11727) 2xn 타일링 2

https://www.acmicpc.net/problem/11727

문제 개요:
11726번의 타일링 문제와 거의 유사하지만, 구성할 수 있는 2*2 타일이 하나 더 늘었다.

문제 풀이:
조합 식은 거의 유사하지만, 가로로 두개 또는 22 타일을 하나로 가정하고 가능한 경우의 수를 모두 구한 후, 22크기의 타일을 구성할 수 있는 종류가 2개 이므로 2의 제곱을 그 경우에 수에 곱해서 모든 경우의 수를 구해야 한다.
하지만, 우리는 간단한 식을 구해야 하므로 ...
이전의 식을 참고 해 조합 피라미드를 그려보니 쉽게 새로운 식을 만들어볼 수 있었다.

p(n) = p(n-1)+ 2*p(n-2)

자세한 풀이

code

#include <iostream>
using namespace std;

int main(){
    int n;
    int arr[1000]={0,};
    //p(1) = 1
    arr[0] = 1;
    //p(2) = 3
    arr[1] = 3;
    cin>>n;
    for(int i=2;i<n;i++){
        arr[i] = (arr[i-1]+2*arr[i-2])%10007;
    }
    cout<<arr[n-1]<<endl;

}

느낀점

1. 그런데,,, 왜인지 경우의 수는 너무 어렵다. 저 피라미드를 그리지 않았으면, 이렇게 쉬운 접근 방법이 있는 줄 몰랐을 것이다. 어떻게 해야 경우에 수를 더 쉽게 떠올릴 수 있을까?
2. 피라미드 어떻게 저렇게 나올 수 있는 건지 너무 궁금하다. 피라미드 너 뭐 돼?