2×n 타일링
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞은 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 256 MB | 34276 | 12623 | 9527 | 34.894% |
문제
2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.
아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.
입력
첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)
출력
첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.
예제 입력 1
1
2
예제 출력 1
1
2
예제 입력 2
1
9
예제 출력 2
1
55
풀이
dp를 구할때마다 10007으로 나눈값을 저장시켜야 하는데
마지막 결과값만 10007으로 나누려해서 틀렸었다. 조심하기 !
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
using namespace std;
int dp[1001];
int main(){
int n ; cin >> n;
dp[0]=1;dp[1]=1;
for(int i=2;i<=n;i++){
dp[i]=dp[i-1]+dp[i-2];
dp[i]%=10007;
}
cout << dp[n] << '\n';
//cout <<dp[n] %10007 << '\n';
}