[백준 11726번] - 2xn 타일링(C++)

11726번: 2×n 타일링

[문제 설명]

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

---

[문제 풀이]

다이나믹 프로그래밍에 대한 감을 잡기에 좋은 문제같다.

다른 DP문제와 같이 규칙을 찾아 점화식을 세우면 된다.

문제 설명을 보면 2x1, 1x2 두개의 타일만 있는 상황이다.

길이가 1일때는 2x1 타일 하나를 두는 1가지 경우가 있다.

길이가 2일때는 2x1 두개, 1x2 두개를 두는 2가지 경우가 있다.

길이가 3(n)일때 우리가 타일을 둘 수 있는 경우는

길이가 2(n-1)일때의 경우(2가지)에서 2x1타일 한개를 추가하는 2가지 방법이 있고,

길이가 1(n-2)일때의 경우(1가지)에서 2x1 2개, 1x2 2개를 추가하는 2가지 방법이 있다.

총 4가지가 있지만, 겹치는 부분이 한부분 생기게 된다.

길이가 2일때 2x1 2개에 2x1 한개를 추가하는 경우와

길이가 1일때 2x1 1개에 2x1 두개를 추가하는 경우이다.

둘다 2x1 3개로 채운 경우가 된다.

길이가 n일때 n-2를 계산하는 경우에서 2x1 두개를 넣는 경우를 제외하면 된다.

그렇다면 우리가 n-2의 경우에서 넣을수 있는 경우는 1x2 2개의 경우 밖에 없다.

따라서 길이가 3일때는 타일을 놓을 수 있는 방법의 수는 길이가 2일때의 경우(2가지) + 길이가 1일때의 경우(1가지)이다.

n일때 채울수 있는 경우의 수는

n-1일때는 2x1 한가지만 넣을 수 있으니 n-1를 채우는 경우 + n-2일때는 1x2 두개를 넣는 경우밖에 없으니 n-2를 채우는 경우

이다.

위 규칙을 통해 우리는 n = n-1 + n-2 를 확인할 수 있다.

이런식으로 우리가 찾는 n이 될때까지 반복하면 된다.

** 파이팅 ! **

코드가 깨끗하고 명확하게 보일진 모르겠지만, 누군가에게 도움이 될 수도.. 있기에..

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

int dp[1001];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int n;
    cin >> n;
    dp[1] = 1;
    dp[2] = 2;
    for(int i =3; i <=n; i++)
    {
        dp[i] = dp[i-1] + dp[i-2];
        dp[i] = dp[i] % 10007;
    }

    cout << dp[n] << "\n";
}