11727: 2Xn 타일링 2

이 문제도 타일링 1문제와 같이 점화식만 찾으면 쉽게 풀 수 있다.

dp[i-2]에서와 dp[i-1]에서 각각 길이가 2개짜리와 1개짜리를 더했을때 나오는 경우의 수를 구하여 

점화식을 만들어보면

 dp[i]=dp[i-1]+dp[i-2]+dp[i-2]가 된다.

 

점화식을 풀 때 dp[1]부터 하나하나 해보면서 구하는 것도 좋지만

dp[i]일때부터 생각해서 일반적인 해의 풀이를 구하는 것이 이 문제에서는 점화식을 더 찾기 쉬운 경우이다.

i-1 덩어리와 i-2 덩어리가 있을 때 i짜리 덩어리를 만들기 위한 경우의 수를 구하면 된다.

 

#include <stdio.h>

int dp[1001];


  int main(void)
  {
   int n;
    scanf("%d",&n);
    dp[1]=1;
    dp[2]=3;
    dp[3]=dp[1]*dp[2]+dp[2]-1;
    
    for(int i=4;i<=1000;i++)
      {
        dp[i]=dp[i-2]*dp[2]+dp[i-1]-dp[i-2]; //2칸 남았을때 가능한 경우의 수 3개, 한칸 남았을때는 1개
        //근데 1개 남았을 때 겹치는 경우가 있음 dp[i-2]에서 세로가 한칸짜리 2개를 붙일 경우
        if(dp[i]>=10007)
          dp[i]%=10007;
      }
    printf("%d",dp[n]);
  }