제가 속했던 팀(the pulza)가 안드로메다로 여행을 떠난 이유 중 하나는 바로 이문제 때문이 아니었을까 싶습니다(실제로도 대회에서는 풀지 못했고, 대회가 끝나고 알고스팟의 중계를 보고 난 직후에야 풀게 되었던 문제입니다.)

하지만 statistics를 봤을 경우 참가한 팀 중에서 21팀이 풀었던 문제인지라 난이도는 그리 어렵지 않다라고 평가를 할 수 있을듯 합니다.

처음에 봤을 때 ICPC계에서 조금이라도 발을 붙이신 분이라면 떠올랐을 문제가 있을 겁니다.

혹시 이 문제를 풀지 못하셨던 분이라면 먼저 추천해드리고 싶은 문제가 있습니다. 아직도 푸시지 못하신 분은 이 문제 부터 풀어보시길 바랍니다.

Tiling : http://acm.pku.edu.cn/JudgeOnline/problem?id=2506

위의 문제는 동적계획법으로 풀 수 있으며, 이 문제를 풀기 위한 점화식은 다음과 같습니다.
D[N] : N길이의 모든 가지수
D[N] = D[N-1] + D[N-2] * 2

E번 문제 역시 동적계획법 문제이지만, 차이점이 있습니다. 그것이 무엇인지 지금부터 설명을 하고자 합니다.

E번 문제가 까다로왔던 이유는 다름이 아니라, 다음과 같은 그림이 동일한 경우인 한가지로 체크가 되기 때문입니다(좌우로 뒤집었을 경우 서로 동일한 모양이 나올 경우)

tile.PNG
* 그림1. 좌우로 뒤집었을 경우 동일한 모양이 나오는 경우

이런 모양이 등장해야하는 조건은 좌우 대칭이 될 수 없는 모양이어야 한다는 것인데요.

위의 조건을 고려하지 않고 모든 경우를 샐 경우에는 저런 모양이 하나 등장하면 반드시 좌우가 뒤집힌 모양이 존재한다는것은 자명합니다. 이러한 사실을 통해 고려하지 않았을 경우의 가지수의 절반이 답이라 생각하고 풀게 되면 예제 조차 나오지 않습니다. 왜일까요?

그것은 아래 그림과 같은 좌우 대칭을 이루는 모양이 존재하기 때문입니다.

tile2.PNG
* 그림2. 대칭 모양을 이루는 경우

대칭을 이루는 경우에는 위와 다르게 한가지만 존재합니다.

따라서 문제에서 요구한 모양의 가지수를 따지기 위해서는 다음과 같은 방식으로 계산을 해야 제대로 된 답을 출력 할 수 있습니다.
A : 문제에서 요구한 조건을 고려하지 않은 모든 가지수 - 이는 Tiling  문제를 풀때 처럼 구하면 됩니다.
B : 대칭을 이루는 모양의 가지수
C : 좌우로 뒤집었을 경우의 동일한 모양이 나오는 경우의 수
D : 문제에서 요구하는 답
C = (A-B) / 2
D = C + B

마지막으로 남은 것은 대칭을 이루는 모양의 가지수 인데요. 길이 N에 대해서 대칭을 이루는 경우의 수는 다음과 같이 구합니다(여기서 문제 조건을 고려하지않은 길이 N에 대한 모든 경우는 P[N]으로 표기합니다.)

우선 길이가 홀수 일경우엔 1 x 2 타일이 가운데에 세워져 있는 모양일 경우를 기준으로 대칭이 되기 때문에 P[(N-1)/2] 가 대칭을 이루는 경우가 됩니다.
짝수의 경우엔 절반의 모양이 대칭이 되는경우와, 1 x 2 타일이 2개가 눕혀진 모양으로 2 x 2 크기로 가운데에 존재하는 경우 혹은 2 x 2 타일이 가운데에 위치한 경우가 존재하므로 가지수는 P[N/2] + 2 * P[(N-2)/2]가 됩니다.

이것만 해결하면 아래와 같이 간결한 소스코드가 나오게 됩니다. 대회에서 못푼 문제라는 점이 아쉽긴 하지만, 꽤나 재미있는 문제 중에 하나가 아니었나 싶습니다.


이 게시물을..