[Baekjoon] 백준 11727번 2xn타일링2

11762번 2xn타일링 문제 풀이

문제

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

입력

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

출력

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

예제

입력
2
3
12

출력
3
171
2731

코드

#include<iostream>
#include<algorithm>
using namespace std;

int d[1001];
int n;

void bottom_up(int n) {
    for (int i = 2; i <= n; i++) {
        d[i] = d[i - 1] + (2 * d[i - 2]);
        d[i] %= 10007;
    }
}

int top_down(int n) {
    if (n == 1) return 1;
    if (n == 0) return 1;
    if (d[n] > 0) return d[n];
    d[n] = top_down(n - 1) + (2 * top_down(n - 2));
    return d[n] %= 10007;
}
int main() {
    cin >> n;
    d[0] = 1;
    d[1] = 1;
    //bottom_up(n);
    top_down(n);
    cout << d[n]; 
    return 0;
}

해결방법

• 앞에서 해결한 2xn타일링 문제와 유사한 방법으로 풀이한다.
• d[n]은 2xn의 직사각형을 2x1, 2x2의 타일을 사용해서 만들 수 있는 경우의 수이다.
• 2xn의 도형을 만들기 위해서는 세 가지 방법이 사용된다.
  1. 2x1 도형들로 만드는 방법.
  2. 2x1 도형 두 개를 합쳐서(2x2) 도형을 만드는 방법.
  3. 2x2 도형을 사용하여 만드는 방법.
• 첫 번째 방법 사용 : d[n-1]에서 나온 모든 경우에 대해 2x1타일을 붙이는 방법.
• 두 번째 방법 사용 : d[n-2]에서 나온 모든 경우에 대해 2x1타일 두 개를 붙이는 방법.
• 세 번째 방법 사용 : d[n-2]에서 나온 모든 경우에 대해 2x2타일을 붙이는 방법.
• 위에서 작성한 것과 같이 d[n]은 2xn의 직사각형을 만들 수 있는 모든 경우의 수이기 떄문에 타일을 붙인다 해서 경우의 수가 달라지지는 않는다. 따라서 d[n] = d[n-1]+(2 * d[n-1])과 같은 식을 세워 문제를 해결할 수 있다.