[C++] 백준 온라인 저지 11727번 2 x n 타일링 2 풀이

2021.11.07 - [알고리즘 문제 풀이/DP] - [C++] 백준 온라인 저지 11726번 2xn 타일링 풀이

[C++] 백준 온라인 저지 11726번 2xn 타일링 풀이

 

이 문제의 후속작 느낌인데 조건이 하나 더 추가된 문제

 

---

문제

 

2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2×17 직사각형을 채운 한가지 예이다.

 

입력

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)

 

출력

첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

 

 

풀이

 

 11726번과 비슷한데 2×2 타일로 채우는 방법도 추가되어서 점화식 내용을 약간 수정해야 합니다. 

 

n = 1

경우의 수 1

n = 2

경우의 수 3

n = 3

경우의 수 5

n = 4

경우의 수 11

 

 3번까지 생각해 보면 피보나치 점화식과는 다르게 증가가 되는 것을 알 수 있습니다. 그럼 새로운 규칙을 찾아봐야 합니다. 일단 n = 3일 때엔 5를 만들려면 1*2 + 3 하면 됩니다. 하지만 이것만으로 점화식을 짜기엔 근거가 좀 약합니다. 좀 더 확실한 근거를 찾기 위해서 2 x n 크기의 사각형을 채우는 경우를 생각해 보겠습니다. 

 

1) n-1 크기의 사각형에 가로 길이가 1인 2x1 크기의 사각형만 붙일 수 있습니다.

 

 

2) 위 그림처럼 각종 방법으로 만들어진 n-2 크기의 사각형들에 각각 2x2 사각형을 붙여서 n 크기의 사각형을 만들 수 있습니다. 그렇기 때문에 항상 n-2 크기 사각형 경우의 수 *2가 된다는 것을 알 수 있습니다. 

 

 그럼 여기서 n = [n-2] * 2 + [n-1] 이라는 점화식을 세울 수 있습니다. 

 

 

코드

 

#include <iostream>
#include <vector>

using namespace std;

const int MOD = 10007;
int main()
{
    int n;
    cin >> n;
    
    vector<long long> DP(n + 1, 0);
    DP[1] = 1;
    DP[2] = 3;
    for (int i = 3; n >= i; i++)
    {
        DP[i] = DP[i-2] * 2 + DP[i-1];
        DP[i] %= MOD;
    }
    
    cout << DP[n];
    
    return 0;
}