문제링크
문제
2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.
아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.
입력
첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)
출력
첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.
풀이
다이나믹 프로그래밍을 이용하여 풀이하였다.
다이나믹 프로그래밍을 사용하기 위해서는 현재 항을 어떻게 이용하여 다음 항을 찾을지에 대한 점화식을 찾는 것이 가장 중요하다.
나의 경우는 직접 그림을 그려보며 점화식을 찾아보았다.
n=1 일 경우 → 1가지
n=2 일 경우 → 2가지
n=3 일 경우 → 3가지
n=4 일 경우 → 5가지
n=5 일 경우 → 8가지
인 것을 찾았고 피보나치 수열일 것 같다는 생각이 들었고, 문제에서 주어진 예제를 통하여 입력이 9일 경우 55가 나오는 것을 보고 확신할 수 있었다.
dp[i] = dp[i-2] + dp[i-1]이라는 점화식을 이용하여 문제를 풀이할 수 있다.
코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
#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] = 2;
for (int i = 3; i <= n; i++) {
dp[i] = (dp[i - 2] + dp[i - 1]) % 10007;
}
cout << dp[n];
}
|
cs |
