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

1. 개요

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

11727번: 2×n 타일링 2

1-1. 설명

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

1-2. 제한 사항

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

---

2. 구현

2-1. 풀이

Dynamic Programing을 이용하여 풀면 된다. 점화식은 n이 1일때부터 타일을 배치하여 점화식을 찾았다. 점화식은 DP[n] = DP[n-1] + DP[n-2] * 2 임을 알 수 있다. n에서 1과 2는 반드시 초기화해주고 진행해주어야 한다. 

2-1. 코드

#include <iostream>
using namespace std;

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

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

    int N;
    cin >> N;

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