기차 여행 (http://boj.kr/10713) 문제 설명이 복잡한데, 결국 각 철도에서 티켓을 사용할지 IC카드를 사용할지를 결정하는 문제이다. 뭐가 더 나은지 확인하려면 i번 철도를 사용한 횟수가 Ki라고 하면 min(Ai×Ki,Bi×Ki+Ci)의 합이 답이다.나는 철도를 몇 번 사용하는지를 저번 글처럼 펜윅트리를 썼는데, 생각해보니 구해놓고 다시 업데이트할 일은 없으니 배열로 해도 된다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455#include int n, tree[100001], ..
증가하는 부분 수열 (http://boj.kr/13555) 앞의 원소부터 차례대로 원소의 값을 인덱스로 해서 배열에 저장해두면, 현재 원소의 값보다 작은 인덱스에 저장된 것들은 현재 원소보다 앞에 있고 작은 것들이라는 의미이다. 이 방법으로 개수도 구할 수 있다.Dij를 i번째 항으로 끝나는 길이가 j인 증가하는 부분 수열의 개수라고 할 때, 앞의 방법대로 구할 수 있다.인덱스가 작은 항부터 넣을 때, 길이가 j인 수열을 만들려면 자신의 값보다 앞에 있는 것들 중 길이가 j−1인 것들에 현재 원소를 붙여야 한다. 즉, 자신의 값보다 앞에 있는 것들의 길이가 j−1인 수열 개수의 합이다. \(D_{i j}=D_{k j-1}(k=1, 2, 3, \cdots,..
암호 (http://boj.kr/10160) ABCBC 또는 ABABC가 포함되지 않도록 암호를 만들어야 한다.이 부분에서 아이디어를 얻어, 암호를 끝자리에 따라서 분류해서 불가능한 암호를 안 만들도록 한다. ABCBC를 안 만들기 위해서는, 끝 자리가 ABCB일 때 C를 안 붙이면 된다.ABCB인 경우를 알기 위해선 ABC인 경우에서 B를 붙이면 된다.ABC인 경우를 알기 위해선 AB인 경우에서 C를 붙이면 된다.... 이런 식으로 경우를 나눠보면,d[i][j]를 j번 경우로 끝나는 i자리 암호라고 했을 때,0번 경우 -> ABCB로 끝나는 경우1번 경우 -> ABC로 끝나는 경우2번 경우 -> AB로 끝나는 경우3번 경우 -> A로 끝나는 경우4번 경우 -> ABAB로 끝나는 경우5번 경우 -> AB..
색상환(http://boj.kr/2482) 먼저, 원형이 아닌 선형일 때의 경우의 수를 찾는다. 선형인 경우는 k가 0일 때 1, k가 1일 때 n이 된다.그리고, k가 1보다 클 때는 n번째 색을 고르는 경우와 안 고르는 경우로 나눌 수 있는데,n번째 색을 고르면, 색이 n-2개일 때 k-1개를 고른 경우이고,n번째 색을 고르지 않으면, 색이 n-1개일 때 k개를 고른 경우이다.둘을 합치면 색이 n개일 때 k개를 고른 경우를 알 수 있다. 그리고 이 것을 원형으로 바꾸기 위해서는, 선형의 색의 양 끝을 잇는다고 생각할 수 있다.이을 때 양 끝이 모두 칠해져 있으면 불가능한 경우이므로, 이 경우를 피하기 위해서 끝의 색 중 하나를 정한다고 생각한다.그리고, 이 색을 고르는 경우와 고르지 않는 경우로 나눌..
줄서기 (http://boj.kr/14864) 먼저, 카드를 순서대로 1, 2, 3, 4, 5, … 순서로 준다고 가정한다.그러면 모두가 자신의 왼쪽보다는 크고 오른쪽보다는 작은 상황이 된다. 이 상황에서 (a, b)라는 입력이 들어오면, b가 a보다 작아야 한다는 것이 된다.입력이 올바르다는 가정 하에, b를 1 줄이고 a를 1 늘리며 번호를 완성해갈 수 있다. 입력이 올바르지 않다면 위의 과정을 반복했을 때 모순된 결과가 나오게 된다. 123456789101112131415161718192021222324252627282930313233#include int cnt[100001];bool chk[100001]; int main() { int n, m, u, v; scanf("%d %d", &n, &m..
서울에서 경산까지(http://boj.kr/14863) 냅색문제처럼 경로 둘 중 하나를 골라서 쌓는다는 느낌으로 구하면 된다. 나는 D[i][j] = i번째 경로까지 j분 이하의 시간으로 얻을 수 있는 최대 모금액이라고 정하고 풀었다.그러면 식은,D[i][j] = max(D[i - 1][j - 도보로 걸리는 시간] + 도보로 모으는 모금액, D[i - 1][j - 자전거로 걸리는 시간] + 자전거로 모으는 모금액)이 된다.하지만 이런 식으로 하면 i - 1번째 경로까지를 j - 시간만에 갈 수 있는지를 따로 확인해야한다. 12345678910111213141516171819202122232425262728#include using namespace std; int tme[101][2], money[101..
문명 (http://boj.kr/14868) BFS로 지도를 채워가면서 유니온 파인드로 문명을 구별해가면 된다. 확장할 때, 인접한 곳이 이미 채워져 있다면 다른 문명인지 확인하고,안 채워져 있다면 문명을 확장하고 그 확장된 곳에 다른 문명이 인접해 있는지를 확인한다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293#include using namespace std; int mp[2001][2001], pr[100001], rnk[1000..
물통 (http://boj.kr/14867) 물을 A에서 B로 옮기던지, B에서 A에서 옮기던지 상관 없이 옮긴 후의 상태는 4가지가 된다. 1. A가 비어있음2. A가 가득참3. B가 비어있음4. B가 가득참 그렇기 때문에 모든 경우를 확인해도 2A+2B가지의 경우밖에 없기 때문에 시간초과가 나지 않는다. 다른 방법은, A에서 B로 물을 옮기고, 그 후에 B에서 A로 물을 옮기는 것은 최단의 방법일 가능성이 없다.마찬가지로 B에서 A로 물을 옮긴 후 A에서 B로 물을 옮기는 것도 가능성이 없다.A에서 B로 물을 옮기는 것을 기준으로 하면, A가 비었다면 물을 채우고, B가 가득 찼다면 물을 버리고, 그렇지 않다면 물을 옮기는 식으로 찾아가면 빠르게 구할 수 있다. 123456789101112131415..