문제

2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)

출력

첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

---

1. 해결방법 및 소스코드

• Dynamic Programming (동적 프로그래밍, 동적 계획법)을 활용하여 점화식을 구한 후 해결했다.
• n == k일 때 직사각형을 채우는 방법의 수를 dp[k]라고 하면, 다음과 같은 점화식이 성립한다.

$\begin{cases}dp[1] = 1\\dp[2] = 2\\dp[k] = dp[k-1] + dp[k-2] (k >= 3)\end{cases}$

• 이를 소스코드로 옮기면 다음과 같다.
• 여기서 주의해야 할 점은 dp배열에 값을 저장할 때 그 값이 매우 커질 수 있으므로 10,0007로 나눈 나머지 값을 저장해야 한다는 것이다.

#include <iostream> using namespace std; int getResult(int n, int dp[]) { if (n <= 2) { return dp[n]; } else { for (int i = 3; i <= n; i++) { dp[i] = (dp[i - 1] + dp[i - 2]) % 10007; } return dp[n]; } } int main() { int n, result; scanf("%d", &n); int dp[n]; dp[0] = 0; dp[1] = 1; dp[2] = 2; result = getResult(n, dp); printf("%d\n", result); }