백준 / 11726번 / 2×n 타일링 / C++

# 출처 : https://www.acmicpc.net/problem/11726

2xN 크기의 타일에 대해 2x1 타일과 1x2 타일로 채울 수 있는 모든 경우의 수를 계산하는 문제이다.

N = 1일때, 2일때 ... 쭉 경우를 열거하여 그 때의 수를 세 보니

N = i 번째 일 때의 경우의 수는 (i - 1일때의 경우의 수) + (i - 2일때의 경우의 수) 라는 규칙을 도출해 내었고

이를 그대로 구현만 하였다.

DP에 관련된 문제는 점화식을 도출 해 내는 등 수학적 관계식을 도출해 내어 푸는것 같은 생각이 점점 든다.

# 풀이 : 

#include <iostream>
using namespace std;
int N, cnt[1001];
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cnt[1] = 1;
    cnt[2] = 2;
 
    for (int i = 3; i <= 1000; ++i)
    {
        cnt[i] = (cnt[i - 1] + cnt[i - 2]) % 10007;
    }
    
    cin >> N;
    cout << cnt[N] << '\n';
    return 0;
}