백준 11727번 2xn 타일링 2

문제 링크 : www.acmicpc.net/problem/11727 

11727번: 2×n 타일링 2

문제 풀이는 다음과 같다. 

 

1. 2x1, 1x2, 2x2타일이 존재한다. 이때, 배열의 맨 마지막을 채우는 방식은 아래와 같다.

2. 잘보면 2x1을 사용해서 채울때와 2x2를 사용해서 채울때는 결국 동일한 케이스에 해당된다.

3. 때문에 점화식을 새울때 arr[n-2]를 두 번 더해준다. 결론적으로 arr[n] = arr[n-1]+arr[n-2]+arr[n-2]가 된다.

 

#include <iostream>
using namespace std;

int n = 0, arr[1001];

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    
    cin >> n;
    arr[0] = 1;
    arr[1] = 1;
    arr[2] = 3;
    for(int i=3; i<=n; i++) arr[i] = (arr[i-2]+arr[i-1]+arr[i-2])%10007;
    cout << arr[n] << "\n";
    return 0;
}