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

백준의 2xn 타일링(11726) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

2xn 크기의 직사각형을 2 x 1 타일과, 1 x 2 타일로 채우는 방법의 수를 구하는 문제이다.

먼저 크기가 작은 직사각형부터 알아보고 이를 통해서 하나의 정형화된 식을 도출해보자.

가장 먼저 2 x 1 크기의 직사각형을 채우는 방법의 수를 구해보자.

2 x 1 크기의 직사각형이니, 1 x 2 로는 채울 수가 없고, 2 x 1 크기의 직사각형 한 개를 이용해서 채우는 방법 한 가지가 있다.

2 x 1 크기의 직사각형 = 1가지

2 x 2 크기의 직사각형을 구해보자. 2 x 2 직사각형의 경우 다음과 같이 2가지 방법으로 채울 수가 있다.
.

위의 그림과 같이 1 x 2 타일을 2개 이용하는 방법과 , 2 x 1 타일을 2개 이용하는 방법 총 2가지 방법이 존재한다.

2 x 2 크기의 직사각형 = 2가지

그럼, 2 x 3 크기의 직사각형을 채워보자.

.

위와 같이 3가지 방법으로 2 x 3 크기의 직사각형을 채울 수 있다.

그런데 위의 그림은 다음과 같은 그림으로 생각해 볼 수 있다.

.

가장 왼쪽 그림부터 1번 , 2번 , 3번 그림이라고 가정해보자.

그런데 1번 그림과 2번 그림은 공통된 부분이 하나 있다. 바로 "2 x 3 직사각형을 채우기 위해서 , 2 x 2 직사각형의 가장 오른쪽에 2 x 1 타일을 추가한 것" 이라는 것이다.

물론 ! 1번 그림과 2번 그림에서 왼쪽에 있는 2 x 2 직사각형을 채우는 방법은 달랐지만 , 그 방법이 어떤 방법이든지 간에 가장 오른쪽에 2 x 1 타일을 하나 더 추가한 형태를 가지고 있게 된다.

그럼 3번 그림은 어떤 특징을 가지고 있을까 ?? 바로 "2 x 3 직사각형을 채우기 위해서 , 1 x 2 짜리 타일을 2개 추가한 것" 이라는 특징을 가지고 있다.

이 정도만 알고, 2 x 4 크기의 직사각형을 채워보자. 2 x 4 크기의 직사각형은 다음과 같은 방법으로 채울 수 있다.

위와 같이 5가지 방법으로 채울 수가 있다. 위의 그림을 다시 한번 특징을 볼 수 있도록 가져와보면 다음과 같다.

마찬가지로 왼쪽에서 부터 1 ~ 5번의 그림이라고 표현해보자.

1번 ~ 3번 그림은 공통된 특징을 하나 가지고 있다.

바로, "2 x 4 직사각형을 채우기 위해서 , 2 x 3 직사각형의 가장 오른쪽에 2 x 1 타일을 추가한 것" 이라는 것이다.

4번 ~ 5번 그림 또한 공통된 특징을 하나 가지고 있다.

바로, "2 x 4 직사각형을 채우기 위해서 , 2 x 2 직사각형의 가장 오른쪽에 2 x 2 타일을 추가한 것" 이라는 것이다.

위에서 이야기했던 2 x 3 직사각형을 채울 때와, 2 x 4 직사각형을 채울 때를 잘 비교해보면 하나의 정형화된 식을 생각해볼 수 있다. 바로 2 x N 크기의 직사각형을 채울 수 있는 방법의 수는 2 x (N - 2) 크기의 직사각형을 채울 수 있는 방법의 수 + 2 x (N - 1)크기의 직사각형을 채울 수 있는 방법의 수 라는 것이다.

위의 식이 적용이 되는지 직접확인해 보자.

2 x 1 크기의 직사각형을 채우는 방법의 수 = 1 가지

2 x 2 크기의 직사각형을 채우는 방법의 수 = 2 가지

2 x 3 크기의 직사각형을 채우는 방법의 수 = 3 가지 = 2 x 1 크기의 직사각형을 채울 수 있는 방법의 수(1) + 2 x 2 크기의 직사각형을 채울 수 있는 방법의 수(2)

2 x 4 크기의 직사각형을 채우는 방법의 수 = 5가지 = 2 x 2 크기의 직사각형을 채울 수 있는 방법의 수(2) + 2 x 3 크기의 직사각형을 채울 수 있는 방법의 수(3)

위의 식이 그대로 적용되는 것을 확인할 수 있다.

2 x (N - 2)크기의 직사각형을 채울 수 있는 방법의 수와, 2 x (N - 1)크기의 직사각형을 채울 수 있는 방법의 수를 단순히 더하는 이유는 우리가 구하고자 하는 값이 "해당 크기의 직사각형을 채울 수 있는 "방법의 수" 이기 때문이다. "사용한 타일의 갯수" 가 아니기 때문이다."

즉, 2 x N 크기의 직사각형을 채울 수 있는 방법의 수는 2 x (N - 2)크기의 직사각형을 채운 상태에서, 1 x 2 크기의 타일을 2개를 붙이는 경우와 2 x (N - 1)크기의 직사각형을 채운 상태에서, 2 x 1 크기의 타일을 1개를 붙이는 경우이다.

따라서 본인은 위의 내용을 구현하기 위해서 DP[] 라는 1차원 배열을 사용해 주었는데, DP[a] = b의 의미는 "2 x a 크기의 직사각형을 채울 수 있는 방법의 수는 b가지 입니다." 를 의미한다.

가장 먼저 초기식으로는 DP[1] = 1과 DP[2] = 2를 설정해주었다.

점화식으로는 위에서 도출한 결과인 DP[N] = DP[N - 1] + DP[N - 2] 로 설정해 주었다.

이해를 돕기위해서 위의 그림과 이 점화식을 같이 표현해보면 다음과 같이 표현할 수 있다.

아래의 그림은 2 x 4 크기의 직사각형을 채우는 방법이다.

. 위와 같이 표현해볼 수 있다.

다시한번 정리하자면, 2 x N 크기의 직사각형을 채울 수 있는 방법의 수는, 2 x (N - 2) 크기의 직사각형을 채워놓고, 그 오른쪽에 1 x 2 크기의 직사각형 2개를 붙이는 경우와 2 x (N - 1)크기의 직사각형을 채워놓고, 그 오른쪽에 2 x 1 크기의 직사각형 1개를 붙이는 경우의 합으로 나타낼 수 있다.

[ 소스코드 ]

#include <iostream>
 
#define endl "\n"
#define MAX 1010
#define MODULER 10007
using namespace std;
 
int N;
int DP[MAX];
 
void Input()
{
    cin >> N;
}
 
void Solution()
{
    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] % MODULER;
    }
    cout << DP[N] << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}