[algospot][ASYMTILING] 비대칭 타일링

문제 : https://algospot.com/judge/problem/read/ASYMTILING

---

DP로 풀었다.

먼저 가능한 모든 경우의 수를 구해서 dp 배열에 저장한다.

dp[i] = 사각형의 너비가 i일 때 가능한 타일링 방법의 수
      = dp[n - 1] + dp[n - 2]

점화식은 위와 같다.

dp[n-1]은 현재 칸에 1 * 2를 채울 때 가능한 타일링 방법의 수이고

dp[n-2]는 현재 칸과 다음 칸에 2 * 1 타일들로 채울 때 가능한 타일링 방법의 수이다.

 

모두 가능한 경우를 구했으면 대칭한 타일링 방법의 수를 구한다.

대칭한 경우

대칭한 경우는 위와 같다.

빨간색 부분과 파란색 부분이 같으면 대칭한 경우이다.

 

위 2개는 짝수인 경우이다. 짝수인 경우 반으로 나눈 부분(N/2)이 같은게 나올 때와 반으로 나눈 것 -1(N/2 - 1) 타일을 같은게 나올 때 가운데 2 * 1 타일 2개를 놓을 때 대칭한 경우이다.

홀수인 경우는 가운데 1 * 2 타일을 놓고 양쪽에 같은 타일로 채웠을 때가 대칭한 경우이다.

// 짝수인 경우
int sym = dp[N/2] + dp[N/2 - 1];

// 홀수인 경우
int sym = dp[N/2];

대칭한 경우를 구했으면 총 타일의 수에서 대칭한 경우의 수를 빼면 비대칭한 타일의 방법의 수를 구할 수 있다.

 

주의할 점은 경우의 수가 무척 크므로 1,000,000,007로 나눈 나머지를 저장해야 하는데 빼기 연산을 하면 올바른 정답이 나오지 않을 수 있다.

따라서 빼기 연산을 할 때는 반드시 양수가 나오게 1,000,000,007을 한 번 더해주고 빼준다.

 

시간 복잡도는 dp 배열을 다 채우는데 걸리는 시간인 O(N).

---

소스코드 : https://gist.github.com/fpdjsns/9551b310c588f495c9f9532867e79a56