백준 11726, 2xn 타일

문제

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

아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.

입력

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

출력

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

예제 입력 1 

2

예제 출력 1 

2

 

예제 입력 2 

9

예제 출력 2 

55

 

 다이나믹 프로그래밍을 활용하여 풀 수 있는 문제다. 이 문제의 경우 2xn의 직사각형을 채울 수 있는 경우의 수는 2x(n-1)의 직사각형을 채울 수 있는 경우 (이 경우 2x1 블럭이 뒤에 추가됨) + 2x(n-2)의 직사각형을 채울 수 있는 경우(이 경우 1x2 블럭 2 개가 추가됨) 이라 할 수 있다. 연쇄적으로 2x1인 경우부터 차례로 구하면 원하던 2xn의 경우 수에 대해 구할 수 있다.

 

1. 입력을 받는다.
2. 2x1, 2x2의 경우 수를 구한다.
3. 2x3 부터 연쇄적으로 경우 수를 구한다. (단 넘칠 수 있으니 미리 모듈러 연산은 해두었다.)
4. 결과를 출력한다.

 

 코드는 다음과 같다.

 

#include <iostream>

int main()
{

    int n;
    std::cin >> n;

    int cases[1001] = {0,  };
    cases[1] = 1;
    cases[2] = 2;

    for (int i = 3; i <= n; i++)
    {
        cases[i] = (cases[i - 1] + cases[i - 2]) % 10007;
    }

    std::cout << cases[n];

    return 0;
}

 

 다이나믹 프로그래밍을 이용한 문제였다. 이 것으로 글을 마친다.