굉장히 오랜 시간이 지나고, 드디어 10번째? 맞나? 아무튼 글을 쓴다. 사실 이렇게 글을 올리는 시간이 늦어진 데에는 타당한 이유가 있는데, 그만큼 필자가 배울 수 있으면서 아주 웰노운은 아닌 아이디어들이 줄어들고 있다는 것이다... 솔직히 쓰라고 하면 쓸 수 있는 것들을 많긴 하지만 그동안 여러개의 주제를 하나로 묶어서 글을 올렸다보니 소재가 빨리 고갈되었다고 생각한다. 따라서 앞으로는 그냥 하나의 주제를 올리는 대신 조금 더 글을 작성하는 기간을 단축해볼까한다.
아무튼, 이번 글에서 다룰 테크닉은 사실 그 이름이 실제로 존재하는 테크닉은 아니고, 그냥 general idea중 하나로 생각할 수도 있다. 그러나 이 아이디어를 발상하지 못하는 이상 문제를 해결하기 극도로 어렵기 때문에 이렇게 정형화된 하나의 테크닉으로 소개하면 좋겠다고 생각했다.
1. Introduction
우선, 기본적으로 풀 문제는 다음과 같다: 8449번: Czekolada (acmicpc.net)
문제를 간단히 요약하자면, 격자판의 어떤 위치에 점이 찍혀있을 때, 격자판을 더 작은 격자판으로 축소하다가 점을 제거하는 사람이 패배하는 게임인데, 여기에서 당신은 선공이 지게 되는 점의 개수를 구해야 한다.
우선, 이 문제의 풀이를 알기 위해서는 스프라그 그런디적인 관찰이 필요하긴 한데, 그냥 중간과정은 전부 건너뛰고 문제를 축소해보면 $ (x)^(n-x)=(y)^(m-y) $를 만족하는 (0<=x<=n,0<=y<=m)의 쌍의 개수를 구하는 것이다(아마 스프라그 그런디 정리를 적용해보면 어렵지 않게 확인할 수 있을 것이라 생각한다.)
그렇다면, 저 값을 어떻게 구해야 할 것인가? 대충 생각해봐도 해당 값을 계산하는 것은 그렇게 간단해보이지는 않는다.
사실, 이 값은 비트에 대한 dp를 통해서 계산이 가능하다. dp[n][m]을 위 조건을 만족하는 그런 x,y의 쌍의 개수라고 하면, 이제 우리는 그리 어렵지 않은 dp식을 얻을 수 있다:
1. n, m의 기우성이 다른 경우: 이 경우에는 자명히 조건을 만족하는 x,y가 없다. 따라서 dp[n][m]=0.
2. n,m이 둘 다 홀수인 경우: 이 경우에는 총 4개의 케이스를 고려해야 한다: x가 홀수/짝수인 경우와 y가 홀수/짝수인 경우
만약 우리가 이번 dp값을 계산하는데에 있어서 x와 y의 첫번째 비트만 결정해준다면, 실제로 (x,y)=(0/1,0/1)과 같은 4가지가 될 것이고, 그 경우들 전체에 대해서 우리가 구해야 하는 나머지 값은 dp[n/2][m/2] 뿐이다(왜냐하면, (n-1)/2 혹은 n/2가 첫 번째 비트를 제외한 나머지 부분이 될 것이기 때문이다.).
따라서 dp[n][m]=4dp[n/2][m/2].
3. n, m이 둘 다 짝수인 경우: 사실 이 경우도 2번이랑 비슷하게 하면 된다. 단지 x,y에 따라 n을 n/2-1로 바꿀지, n/2로 바꿀지가 갈릴 뿐이다.
2. Square counting technique
사실, 여기까지만 보면 이 글에서 소개할 square counting technique의 진정한 의미를 해석하기 어려울 수 있다. 이제 square counting technique가 무엇을 구하는 아이디어인지 간략히 설명해보면, 간단히 말해 sum(S: 나올 수 있는 모든 상태)(num(S)^2)을 구하는 아이디어이다. 즉, 등장 가능한 모든 상태들에 대해서 상태의 개수의 제곱을 전부 합하는 문제를 해결하는 아이디어이다.
내가 왜 이 문제를 소개했냐면, n=m일때 정확히 이 아이디어가 적용되는 예시로 생각할 수 있기 때문이다. 물론 해당 문제가 square counting technique가 직접적으로 적용되는 예시는 아니다.
이제 다음과 같은 문제를 생각하자: 17333번: Pipe Marbles (acmicpc.net)
문제는 요약하기 귀찮은 관계로 읽기를 권장한다.
아무튼, 이 문제에서는 가능한 모든 상태에 대해, 상태의 개수의 제곱의 합을 구하는 것을 요구하고 있다. 그냥 단순하게 생각하면 해당 문제를 푸는 것은 굉장히 까다롭다. 그러나, 우리가 위에서 보았던 아이디어를 활용하면 이 문제를 해결할 실마리를 얻을 수 있다.
상태의 개수의 제곱을 구하는 문제 대신, 문제를 확장해서 파이프 2쌍이 총 두 개 존재하고, 각각의 파이프쌍에서 원소들을 추출해서 "동일한 문자열"을 만드는 문제로 확장할 수 있다. 즉, 파이프는 총 4개 존재하고 결과파이프가 2개 있으며, 우리의 목적은 결과파이프에 동일한 문자열이 존재하는 가짓수를 세는 것이라고 볼 수 있다.
만약 이 문제를 해결할 수 있다면, 그냥 문제에서 주어진 파이프를 복사한 다음에 확장된 문제를 풀면 그것이 원하는 답임을 알 수 있다.
그리고, 우리가 맨 처음에 다뤘던 문제의 철학에 입각하여 생각해보면 우리는 dp[len][n][m]=두 파이프쌍에서 각각 len번째 원소까지 결정했고, 첫 파이프쌍의 첫번째 파이프에서 n개 꺼냈고, 두번째 파이프쌍의 첫번째파이프에서 m개 꺼낸 경우 이 두 문자열의 결과가 동일하도록 원소를 뽑는 방법의 수와 같이 정의할 수 있다. 그리고 이건 그냥 단순히 현재 맨 끝부분에 있는 문자들의 타입에 따라 더해주면 됨을 알 수 있다. 따라서 전체 문제가 해결된다.
결국, 이 테크닉이 알려주는 insight는 총 두 가지가 있다.
첫번째는, 문제를 특정한 방향으로 확장하는 것은 생각보다 쓸만하다는 것.
두번째는, 제곱의 합이라는 것에 담긴 조합론적 의미이다.
뭐어, 사실 이런 유형의 문제 말고 이런 아이디어를 적용 가능한 곳이 어디에 있을지는 솔직히 나도 모르겠다... 그냥 이런 유형의 문제가 나오길 기도하고 나오면 풀면 되는것 아닐까?
3. Exercise
연습 문제로는 다음이 존재하는 것으로 추정되지만, 필자도 해당 문제를 아직 해결하지는 못하였다...
18345번: 순례자의 기억과 감명받은 신 (acmicpc.net)
아무튼 최근에 문제를 풀다가 두번이나 조우한 아이디어인 만큼 신기해서 이렇게 글로 써보았다. 만약 이 아이디어의 이름을 아는 사람이 있으면 제보를 부탁한다...
