점 연결하기 (BOI 2007)

https://www.acmicpc.net/problem/2434

http://koistudy.net/?mid=prob_page&NO=375

모든 점을 통괄하는 경로는 교차할 수 없기 때문에, 윗바닥과 아랫바닥을 먹는 두 선이 갈린다고 생각할 수 있다. 두 선의 상태는 그렇게 많지는 않아서, 이 "두 선"을 바탕으로 점화식을 세우는 것이 좋을 것이다. 나의 경우에는 다음과 같은 세개의 상태가 나왔다.

 * U[i] = i번 줄까지의 원소들을 다 봤고, i+1번째 줄의 위에서 1 - 2번째 원소에 발을 내린, 그 외에는 전혀 건들지 않은 상태

 * M[i] = i번 줄까지의 원소들을 다 봤고, i+1번째 줄의 위에서 1 - 3번째 원소에 발을 내린, 그 외에는 전혀 건들지 않은 상태

 * D[i] = i번 줄까지의 원소들을 다 봤고, i+1번째 줄의 위에서 2 - 3번째 원소에 발을 내린, 그 외에는 전혀 건들지 않은 상태.

다음 상태로 가는데 중요한 것은 발을 안 내린 원소를 어떻게 잘 먹는 것이다. 가령 M[i]에 대해서는 (i+1, 2) 원소를 어떻게 해야지 잘먹냐... 같은 게 중요한 관건이 될 것이다. Z 모양, V 모양으로 해당 원소를 먹을 수 있으며 나머지 경우의 수는 딱히 생각해주지 않아도 되며, 나머지 줄도 거의 일반성을 잃지 않고 동일하게 된다. 세 줄을 나눠줬지만 크게 나눠줄 필요가 없었던 것이다!

이제, U[i] + M[i] + D[i] = S[i]라 하면, 잘 (...) 하면 S[i] = 4S[i-1] + 4S[i-2]임을 알 수 있다. 이제 S[3] = 8, S[4] = 40으로 초항을 잡으면 된다. lgN에 계산하는 건 행렬을 써서 가능하고 설명은 생략하고자 한다.

조심해야 할것은 N = 1 -> 0, N = 2 -> 1이라는 것이다. 이는 식하고 약간 모순되는 부분이고 모서리 부분에서 문제가 생기는 거 같다. 초항을 넉넉히 잡은 이유이기도 하다 ㅠㅠ 이런거 짤 때는 DM 돌려보는게 필수인듯.