[백준] 11727번 2xn 타일링 2

문제

 

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

 

풀이

 

취준생 때 이해하기 힘들어서 포기했던 문제다.

시간을 두고 천천히 그림을 그려가면서 생각해보면 점화식을 생각해낼 수 있습니다.

2x2 타일을 채우는 경우를 그림으로 그려보고, 2x3 을 채우는 방식을 생각해봅니다.

2x3은 앞 쪽에 2x1 타일을 채우고 나머지를 채우는 경우와 뒤 쪽에 2x1을 채우고 나머지를 채우는 경우로 생각 할 수 있습니다.

 

소스코드

 

// boj.kr/11727
// 2xn 타일링

#include <iostream>

using namespace std;

#define MOD 10007

const int MAX_N = 1000;

long long gCache[MAX_N+1];

int main(){

    ios::sync_with_stdio(false);
    cin.tie(0);

    // N = 1 일 때 경우의 수는 1가지.
    // N = 2 일 때 경우의 수는 3가지. 
    
    int n;

    cin  >> n;

    gCache[1] = 1;
    gCache[2] = 2;

    for(int i = 3; i <= n; i++){
        
        gCache[i] = (gCache[i-1]%MOD) + (gCache[i-2]%MOD);
    }

    cout << gCache[n] % MOD << "\n";
    
    return 0;
}