[백준][11726] 2xn 타일링
문제
2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.
아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.
입력
첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)
출력
첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.
입력 1
2
출력 1
2
입력 2
9
출력 2
55
1. 문제 설명
처음봤을땐 이게 뭔가 싶은 문제이다. 하지만 굉장히 단순한 점화식으로 구현가능하다.
위 사진을 보면
n=1
,n=2
를 기본값으로 두고n=3
일 때 부터 규칙성이 보일것이다.
n
의 모양은 자세히 살펴보면n-1
의 모양에서는 세로 막대기 1개가 추가되고,n-2
의 모양에서 가로 막대기 2개가추가된 모습이다.
++(주황색으로 표시한 모양은n-2
, 빨간색으로 표시한 모양은n-1
이다.)++점화식 :
dp[i] = dp[i - 1] + dp[i - 2]
문제에서 10007로 나눈 나머지를 구하라고 하였으니, 점화식 뒤에% 10007
를 적어주면 끝.
2. 소스 코드
#include <iostream>
#include <vector>
using namespace std;
int main() {
const int MOD = 10007;
int n;
cin >> n;
vector<int> dp(n + 2, 0);
dp[1] = 1;
dp[2] = 2;
for (int i = 3; i <= n; i++) {
dp[i] = (dp[i - 1] + dp[i - 2]) % MOD;
}
cout << dp[n] << endl;
return 0;
}