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

백준 11727 : 2 x n 타일링 2

---

2×n 타일링 2 성공

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

1 초

256 MB

23330

13937

11148

59.727%

---

문제

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

아래 그림은 2×17 직사각형을 채운 한가지 예이다.

---

입력

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

출력

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

 

---

 

 

#include<stdio.h>

int main(void)
{
    int input = 0;

    scanf("%d",&input);

    int DP[1001] = {0,};

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


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

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

 

 

 

 

DP 문제를 계속해서 풀어보니 점점 어떻게 풀어야하는지 감이 잡히네요.. 규칙을 찾고 배열의 점화식을 생각하고 마지막 시간초과를 예방하기 위해 배열을 사용하고 문제에서 요구하는 수로 나누어서 출력해주기..등등 얼른 DP문제를 마스터하고 다음 알고리즘으로 넘어가야겠어요!!