문제

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

입력

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

출력

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

풀이

해당 문제는 Dynamic Programmin으로 해결할 수 있는 문제 입니다. 문제의 규칙을 이용해서 점화식을 도출 하도록 하겠습니다.

  1. n=1인경우 2 x 1인 타일을 채우는 경우의 수는 1개 (2x1타일 이용)

    2x1크기의 타일을 2x1타일 1개를 이용해서 채울 수 있습니다.

image.png

  1. n=2인경우 2 x 2인 타일을 채우는 경우의 수는 2개 (2x2타일 이용)
    2x2크기의 타일을 2x1타일 2개를 이용하는 방법, 2x2타일을 2개이용하는 방법으로 총 2가지 경우의 수가 나오게 됩니다.
    image.png
  1. n=3인경우 2 x 3인 타일을 채우는 경우의 수는 3개
    2x3크기의 타일을 2x1타일 3개로 채우는 방법, 2x2타일 2개와 2x1타일 1개, 마지막을 2x1타일 1개와 2x2타일 2개로 채우는 방법으로 총 3가지 경우의 수가 있습니다.
    image.png

  2. n=4인경우 2 x 4인 타일을 채우는 경우의 수는 5개
    아래 그림과 같은 경우의 수를 찾을 수 있습니다.

image.png

  1. 점화식
    2xi 타일을 채우는 경우는 i-1번째경우의 수 + i-2번째 경우의 수를 합하면 구할 수 있습니다.

    dp[i] = ' 2 x i 타일을 채울 수 있는 경우의 수 ' =  dp[i-1] + dp[i-2]
  2. 코드

    #include<stdio.h>
    int dp[10001];
    int main(){
     int i,n;
     scanf("%d",&n);
     dp[0] = dp[1] = 1;
     for(i = 2; i<= n; i++) {
         dp[i] = dp[i-1] + dp[i-2];
         dp[i] %= 10007;
     }
     printf("%d",dp[n]);
     return 0;
    }