[C++] BaekJoon 11726 2×n 타일링

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

---

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

이는 다이나믹 프로그래밍을 이용하여 해결이 가능하며, 이 문제는 피보나치 수열과 유사한 점화식을 따른다.

 

이는 다음과 같다.

 

점화식 유도

2 x n 크기의 직사각형을 채우는 방법은 다음 두 가지로 나눌 수 있다.

I. 세로로 2 x 1타일을 맨 왼쪽에 하나 놓고 나머지를 채우는 방법

II. 가로로 1 x 2 타일을 두 개 놓고 나머지를 채우는 방법

 

따라서, 첫 번째 경우는 2 x (n - 1) 크기의 직사각형을 채우는 방법의 수와 같고, 

두 번째 경우는 2 x (n - 2) 크기의 직사각형을 채우는 방법의 수과 같다.

 

이를 수식으로 나타내면

f(n) = f(n - 1) + f(n - 2)

 

초기 조건

• f(0) = 1 : 2 x 0 크기의 직사각형을 채우는 방법은 아무것도 놓지 않는 하나의 경우이다.
• f(1) = 1 : 2 x 1 크기의 직사각형을 채우는 방법은 세로로 2 x 1 타일 하나를 놓는 방법밖에 없다.

 

코드

#include <iostream>
#include <vector>

using namespace std;

long long countTiling(long long n) {
    vector<long long> dp(n + 1, 0);

    // 초기 조건 설정
    dp[0] = 1;
    dp[1] = 1;

    // 다이나믹 프로그래밍 테이블 채우기
    for (long long i = 2; i <= n; ++i) {
        // 현재 칸을 1x2 타일로 채우는 경우
        dp[i] += dp[i - 1];
        // 현재 칸을 2x1 타일로 채우는 경우
        dp[i] += dp[i - 2];
        dp[i] %= 10007;
    }

    // 전체 문제의 해 반환
    return dp[n];
}

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

    long long n;
    cin >> n;// 직사각형의 너비
    cout << countTiling(n) << "\n";
    return 0;
}