11726) 2×n 타일링

문제

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

입력

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

출력

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

예제 입력

9

예제출력

55

풀이

2n 크기의 직사각형을 채우는 방법의 수(=p(n))를 조합을 이용해 풀었다.
가로로 누운 두 블럭은 0~2/n개까지 존재할 수 있으므로, 가로로 누워있는 블럭 a개와 세로로 서있는 블럭 b개가 나열될 수 있는 경우의 수를 구하면 된다.
p(n)
= sum{from k=0 to n/2} (k+1)H(n-2k)
= sum{from k=0 to n/2} (n-k)C(n-2k)
= p(n-1)+p(n-2)

좀 더 자세한 풀이과정은 그림을 참고

추가) 나중에 찾은 쉬운 풀이

3개를 구성하는 경우의 수를 생각해보면, 맨 앞 타일이 세로 2x1타일이었을 때, 뒤에 2칸을 구성하는 경우의 수는 2를 2x2공간을 구성하는 경우의 수와 같으며, 맨 앞 타일이 가로 두개 2x2타일이었을 때, 뒤 한칸을 구성하는 경우의 수는 2x1공간을 구성하는 경우의 수와 같다. 이 규칙을 일반화하여 다음과 같은 식을 구할 수 있다.
p(n) = p(n-1)+p(n-2)

코드

#include<iostream>
using namespace std;

int main(){
    int n, m,index=0;
    cin>>m;
    int** c= new int*[m+1];
    for(int i=0;i<=m;i++)
        c[i] = new int[m+1];
    
    c[0][0] = 1; 
    for(int i=1;i<m+1;i++){
        c[i][0] = 1;
        c[i][i] = 1;
        for(int j=1;j<i;j++){
            c[i][j] = (c[i-1][j-1]+c[i-1][j])%10007;
        }
    }
1
    int sum=0;
    n=m/2;
    for(int i=0;i<=n;i++){
        // cout<<i<<" "<<c[m-i][m-2*i]<<endl;
        sum+=c[m-i][m-2*i];
        sum%=10007;
    }

    cout<<sum%10007<<endl;

}