문제링크
문제
2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.
아래 그림은 2×17 직사각형을 채운 한가지 예이다.
입력
첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)
출력
첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.
풀이
다이나믹 프로그래밍을 이용하여 풀이하였다.
2xN 크기의 직사각형을 채우는 방법은 아래와 같이 나눌 수 있다.
- 2x(N-1)만큼 채우고 2x1 타일을 붙인다.
- 2x(N-2)만큼 채우고1x2 타일을 두 개 붙인다.
- 2x(N-2)만큼 채우고 2x2 타일을 한 개 붙인다.
위의 내용을 점화식으로 만들면 dp[n-1] + dp[n-2]*2가 된다.
코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
#include <iostream>
using namespace std;
int n;
int dp[1001];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n;
dp[1] = 1;
dp[2] = 3;
dp[3] = 5;
dp[4] = 11;
for (int i = 5; i <= n; i++) {
dp[i] = (dp[i - 2] * 2 + dp[i - 1]) % 10007;
}
cout << dp[n];
}
|
cs |
