조합론 (9) 썸네일형 리스트형 백준 16878 - 궁전 https://www.acmicpc.net/problem/16878 대부분의 평범한 컴퓨터 공학 학부생은 풀 수 없는 문제로 보인다. 이 문제는 Hertzsprung's problem라는 이름으로 알려져 있으며 원본 문제는 각 열과 행에 킹이 하나만 있게 하면서 서로를 공격할 수 없게 배치하는 경우의 수를 구하는 것이다. 다행히도 OEIS에는 제한 시간 안에 충분히 돌아가는 단순한 점화식을 제공하는데 다음과 같다. $dp(0) = dp(1) = 1$ $dp(2) = dp(3) = 0$ $dp(4) = 2$ $dp(n) = (n + 1)dp(n - 1) - (n - 2)dp(n - 2) - (n - 5)dp(n - 3) + (n - 3)dp(n - 4) (n \geq 5)$ 이 점화식으로 동적 계획법을 짜.. 백준 10728 - XOR삼형제 1 https://www.acmicpc.net/problem/10728 대회 에디토리얼에 의하면 이 문제는 백트래킹 사용을 염두에 두고 나온 것으로 보인다. 다만 백트래킹으로 문제를 푸는 것은 그다지 의미가 없다고 판단되어 제한이 더 큰 XOR삼형제 2에도 쓸 수 있는 솔루션을 동일하게 적용했다. 여기에서 확인할 수 있다. 백준 10736 - XOR삼형제 2 https://www.acmicpc.net/problem/10736 수열의 최대 길이 찾기 XOR의 성질에 따라 $V \oplus V = 0$ 이므로 XOR 과정 중 중복되는 수를 만나서는 안된다. 다시 말해 어떤 세 원소를 선택하든 최소 한 개의 비트를 살릴 수만 있으면 된다는 것이다. 그렇다면 100 이하의 수로 구성할 수 있는 수열의 최대 길이는 어떻게 찾을 수 있을까? 32와 64를 이진수로 나타낸 표를 보면서 생각해보자. X 1 0 0 0 0 0 1 0 0 0 0 0 0 이 표에 존재하는 0을 0 혹은 1로 채우는 경우의 수를 만든다고 했을 때 1이 절대로 들어가서는 안 되는 경우가 무엇일까? X 1 0 0 0 0 0 1 NO 0 0 0 0 0 바로 64에서 $2^{5}$에 해당하는 비트이다. .. 백준 1413 - 박스 안의 열쇠 www.acmicpc.net/problem/1413 문제의 상황을 상상해보자. 박스에 열쇠를 넣다 보면 열쇠로 다른 박스를 여는 상황이 마치 방향 그래프를 구성하는 것처럼 보임을 알 수 있다. 5번 박스에 5번 열쇠가 있다면 이는 루프를 가진 그래프가 되는 것이다. 박스와 열쇠의 관계는 여러개의 사이클 그래프가(루프 포함) 나오는 것으로 생각할 수 있고, 이는 제1종 스털링 수로 환원된다. 제1종 스털링 수는 말 그대로 n개의 노드에서 m개의 사이클이 형성되는 경우를 나타내는 수열이다. 제1종 스털링 수의 점화식은 다음과 같다. $s(n, k) = (n - 1)s(n - 1, k) + s(n - 1, k - 1) \; (s(0, 0) = 1)$ 한 사이클을 순회하기 위해선 한 개의 폭탄이 필요함을 알 수.. 백준 1754 - 진영 순열 icpc.me/1754 A[0]이 입력으로 주어진 이유 $A[0] \geq 0$ 인 순열들에 대해 진영 순열로 변환하면 다음과 같은 모양새를 띠게 된다. 0 _ _ _ ... / _ 0 _ _ ... / _ _ 0 _ ... / _ _ _ 0 ... 그러면 a + b = c라고 할 때 c-진영 순열이 되는 경우의 수는 0 왼쪽에 있는 순열이 a - 1 진영 순열인 경우 * 0 오른쪽에 있는 순열이 b-진영 순열인 경우 여기서 0 왼쪽에 있는 순열은 0때문에 기존 진영 순열에서 1 더해지므로 a - 1 진영 순열이어야 한다. A[0]인 경우도 따로 처리해야 한다. 이럴 때는 길이 n의 수열이 c-진영 순열인 경우를 구하면 된다. 진영 순열 구하기 기존에 순열에서 확장하는 것을 생각해보자. 다음 대소 관계를.. 이전 1 2 다음
