(C++) 백준 11726번 - 2xn 타일링

문제 링크 : https://www.acmicpc.net/problem/11726

11726번: 2×n 타일링

풀이

다이나믹 프로그래밍을 사용하여 풀이하였다.

2*N 크기의 타일을 채우는 방법은 제일 처음 1*2 크기의 타일을 먼저 채웠을 경우와 제일 처음 2*1 크기의 타일 2개를 먼저 채우고 시작할 경우의 합이다.

즉 2*(N-1) 크기의 타일을 채우는 방법과 2*(N-2) 크기의 타일을 채우는 방법의 합을 구하면 된다.

#include <iostream>

using namespace std;

int tile[1002];
int n;

int main() {
    ios::sync_with_stdio(0);  
    cin.tie(0);
    cout.tie(0);

    cin >> n;
    tile[0] = 1;
    tile[1] = 2; 

    for(int i = 2; i < n; i++) tile[i] = (tile[i-1] + tile[i-2])%10007; // overflow 방지를 위해 저장할 때마다 나머지를 넣어줌
    cout << tile[n-1];
}