11726 2xn타일링

문제 : https://www.acmicpc.net/problem/11726

11726번: 2×n 타일링

2×n 타일링 성공

시간 제한메모리 제한제출정답맞은 사람정답 비율

1 초

256 MB

50425

18576

13730

34.660%

문제

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

출처

• 문제를 만든 사람: baekjoon

 

<개인풀이>

2n 타일을 그릴 수 있는 박스를 그려놓고 이웃하는 항의 일반항을 찾아서 대입함.

 

#include<stdio.h>
 
int get_dp(int n);
static int dp[1001] = { 1,1};
int main(void)
{
    int ntile;
 
    scanf("%d", &ntile);
 
    printf("%d\n", get_dp(ntile));
}
 
int get_dp(int n)
{
    if (n <= 1) return dp[n];
 
    if (dp[n]>0) return dp[n];
    
    else{
        dp[n] = ((get_dp(n - 1) + get_dp(n - 2)) % 10007);
    }
    return dp[n];
    
}