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

11762번 2xn타일링 문제 풀이

문제

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

입력

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

출력

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

예제

입력
2
9

출력
2
55

코드

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

int d[1001];
int n;

int top_down(int n) {
    if (n == 0) return 1;
    if (n == 1) return 1;
    if (d[n] > 0) return d[n] %= 10007;
    d[n] = top_down(n - 1) + top_down(n - 2);
    return d[n] %= 10007;
}

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

int main() {
    cin >> n;
    d[0] = 1;
    d[1] = 1;
    top_down(n);
    //bottom_up(n);
    cout << d[n];
    return 0;
}

해결방법

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