(C언어) 백준 11726번 : 2×n 타일링 - 컴도리돌이

 

백준 11726번 : 2 X n 타일링

---

문제

2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.

---

입력

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)

출력

첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

---

 

 

#include<stdio.h>

// int DP(int n)
// {
//     if(n==1) return 1;
//     if(n==2) return 2;
//     return (DP(n-1) + DP(n-2))%10007;
// }

int main(void)
{
    int n = 0 ;

    scanf("%d",&n);

    int DP[1010] = {0,};

    DP[0] = 1;
    DP[1] = 1;

    for(int i = 2; i <= n;i++)
    {
        DP[i] = (DP[i-1] + DP[i-2])%10007;
    }

    printf("%d\n",DP[n]%10007);
    
}

 

 

 

 

DP 문제들은 재귀호출로 풀면 시간초과가 자주 일어나기 때문에 배열로 푸시는것을 추천드립니다 ㅠㅠ ..시간 초과 때문에 3번이나 틀렸네요.. 그리고 문제에서 "10007로 나눈 나머지를 출력한다" 이런 문구가 자주 보이는데 이게 다 시간 초과를 예방할려고 힌트를 준거 같더라고요;; DP문제 너무 어려워요..