[BOJ/C++] 2xn 타일링(11726번)

1. 개요

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

11726번: 2×n 타일링

1-1. 설명

2xn 크기의 직사각형을 1x2, 2x1 타일로 채우는 방법의 수를 구하는 프로그램을 작성한다. 

1-2. 제한 사항

 - 첫 줄에 n이 주어지며, n은 1 이상 1,000 이하

---

2. 구현

2-1. 풀이

2xn 타일링 2와 마찬가지로 Dynamic Programming을 진행하였다. 동일하게 1부터 5까지 차근차근 타일을 그려보았으며, 점화식을 찾아 코드로 구현하였다. 

2-2. 코드

#include <iostream>
using namespace std;

constexpr size_t DIV_NUM = 10007;
int dp[1001];

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

    // 1 X 2, 2 X 1
    int N;
    cin >> N;

    dp[1] = 1;
    dp[2] = 2;

    for (int i = 3; i <= N; i++) dp[i] = (dp[i - 1] + dp[i - 2]) % DIV_NUM;
    cout << dp[N];

    return 0;
}