놀이기구1 (http://boj.kr/14434) 먼저, 날짜별로 구하는건 필연적으로 놀이기구들을 다 확인해야 돼서 힘들다고 생각했다. 그래서 놀이기구별로 언제부터 가능한지를 이분탐색으로 찾으려 했는데, 어떤 날에 두 아이의 키가 얼마인지를 바로 알려면 \(NK\)크기의 공간이 필요해서 필요한 것만 남기는 방법을 고민했다. 이 부분은 금방 알아냈다. 각 아이별로 키가 크는 시점만 저장해논 뒤, 이분탐색으로 현재 시점이 각 아이의 몇 번째 성장인지를 찾으면 된다. 이렇게 놀이기구가 가능한 날을 구한 뒤, 그 날의 카운트를 늘려주면 앞에서부터 답을 셀 수 있다풀고나서 찾아보니 parallel binary search라는 기법이였다. 유성문제와 비교했을때 이 풀이가 pbs라고 하기엔 이상한 것 같다... 12..
기념품 (http://boj.kr/12873) 링크드리스트를 이용해 \(t^3\)만큼 뒤로 가서 지워도 되지만, 점화식을 찾을 수 있다.\(n\)명이 있을 때는 \(1^3\)번째 사람이 제외된다. 그 후에, \(n-1\)명이 남았을 때 아까 제외된 사람부터 출발한다. 즉, \(n\)명이 있을 때의 결과는 \(n-1\)명이 있을 때 \(1\)번부터 시작한 결과와 같다. 마찬가지로 \(n-1\)명이 있을때의 결과는 \(n-2\)명이 있을 때 \(1^3+2^3\)번부터 시작한 결과이다.식으로 나타내면, \(i\)명이 있을 때의 결과를 \(D_i\)라고 했을 때, \(D_1=1,\) \(D_i = (D_{i-1} + (n-i+1)^3 - 1) \bmod i + 1\)이다.식이 좀 복잡해보이는데, \(-1\)과 ..
의좋은 형제 (http://boj.kr/2499) 만약 \(i\)번째 열까지에서 합으로 \(k\)를 만들 수 있다면, \(i+1\)번째 열에서 \(k\)에 다음 열의 수를 더한 것도 만들 수 있다. 문제에서 합이 40000을 넘을 일이 없기 때문에, dp로 찾을 수 있다. 앞의 열의 높이가 현재보다 작아야거나 같아야한다는 점에 유의해서 잘 구현하면 된다. 형을 기준으로 했더니, n번째 행부터 시작해서 매우 헷갈린다.마지막에 높이를 찾는 방법은, 가장 오른쪽 열부터 답이 되는 높이만큼의 합을 빼주면서 찾으면 된다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546#include using namespace ..
기차 여행 (http://boj.kr/10713) 문제 설명이 복잡한데, 결국 각 철도에서 티켓을 사용할지 IC카드를 사용할지를 결정하는 문제이다. 뭐가 더 나은지 확인하려면 \(i\)번 철도를 사용한 횟수가 \(K_i\)라고 하면 \(\text{min}(A_i\,\times\,K_i, B_i\,\times\,K_i+C_i)\)의 합이 답이다.나는 철도를 몇 번 사용하는지를 저번 글처럼 펜윅트리를 썼는데, 생각해보니 구해놓고 다시 업데이트할 일은 없으니 배열로 해도 된다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455#include int n, tree[100001], ..
증가하는 부분 수열 (http://boj.kr/13555) 앞의 원소부터 차례대로 원소의 값을 인덱스로 해서 배열에 저장해두면, 현재 원소의 값보다 작은 인덱스에 저장된 것들은 현재 원소보다 앞에 있고 작은 것들이라는 의미이다. 이 방법으로 개수도 구할 수 있다.\(D_{i j}\)를 \(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..