[알고리즘 문제] 백준11726 - 2xn 타일링

https://www.acmicpc.net/problem/11726

11726번: 2×n 타일링

자주 접하는 dp문제이다. dp[n]는 2 x n 크기의 직사각형을 채우는데 필요한 타일의수가 들어간다. 대부분 피보나치수열과 같은 방식으로 문제를 푸는데, 왜 이렇게 푸는지 생각해 보았다(사실 같은 문제를 몇번 푼 것 같은데 그냥 공식으로만 풀었고 왜? 그렇게 되는지는 생각해보지 않았다...)

 

먼저 순열에 대해 생각해보자. 뜬금없지만 문제를 푸는데 도움이 된다. 일단 한번 짚어보고 가자. [1,2,3,4]으로 만들 수 있는 순열을 다음과 같다.

 

1 2 3 4 
1 2 4 3 
1 3 2 4 
1 3 4 2 
1 4 2 3 
1 4 3 2 
2 1 3 4 
2 1 4 3 
2 3 1 4 
2 3 4 1 
2 4 1 3 
2 4 3 1 
3 1 2 4 
.....

 

만약 천의자리가 "1"인 순열의 가지수는 몇개나 될까 ? 천의 자리를 제외한 3개의 숫자[2,3,4]로 순열을 만드는 경우이기 때문에 3!가 된다. 위에서 보면 실제로도 그렇다.

 

이는 천의 자리가 "2,3,4"이든 상관없이 n개의 숫자로 순열을 만들 때 하나의 숫자의 자리가 정해졌을 때 나머지 숫자들로 만들 수 있는 경우의 수는 (n-1)!이 된다. 또한 2개의 숫자가 정해져 있다면 (n-2)!이 된다.

 

다시 문제로 돌아가보면, dp[n]에는 2 x n 크기의 직사각형을 2x1, 1,x2의 타일로 채울 수 있는 방법의 수를 구하는 문제이다.

dp[n]에는 어쨋든 방법의 수, 경우의 수가 들어간다고 했으니 dp[n]에는 위에서 n에 대한 !값이 들어가 있을 것이다. 

이 문제를 위의 순열 문제와 연관지어 보자.

 

위의 문제는 1x2, 2x1 타일로 직사각형을 채우는 것 대신에 1x2, 2x2 타일로 직사각형을 채우는거라고 생각하면 된다.

 

먼저, 결론부터 말하면...직사각형의 가로의 길이가 n인 경우는 (n-1) 경우의수 + (n-2) 경우의 수를 더한 값과 같다.

이제 왜 그런지 한번 알아보자...

 

예를 들어 n이 다음과 같은 경우 1x2, 2x2 타일로 직사각형은 채우는 방법을 생각해 보자.

n=1 : " l " (1x2 타일 하나)

n=2 : " ll ", " = " (2x2 타일 하나)

n = 3 : " lll " , " l= ", " =l ",(1x2타일 1개, 2x2타일 1개)

n= 4 : " llll ", " l=l ", " =ll ", " ll= ", == "

 

여기서 부터 중요하다....n=4인 경우를 생각해보자.

 

1. 첫번째 3가지의 경우( " llll ", " l=l ", " =ll ")는 n=3인 경우에서 제일 오른쪽에 1x2타일을 하나 붙인 것과 모양이 같다. 이를 다르게 말하면 제일 오른쪽 부분은 1x2로 고정되어 있다는 말로 가로의 길이가 4인 직사각형에서 한자리(제일 오른쪽 부분)는 " l "모양으로 고정되어 있다는 의미이다.

 

이는 순열에서 한자리가 고정되어 있을 때 경우의 수는 그 자리를 제외한 (n-1)!의 값과 같다고 하였다. 우리는 (n-1)!을 구하는 대신 그 값은 dp[n-1]에 저장해 놓았다. 그렇기 때문에 dp[n-1]을 더해준다. 여기서 n=3인 경우 2x2 도형을 추가할 수 없다. 왜냐하면 4를 넘어버리기 때문에...

 

2. 위의 경우와 마찬지로 제일 오른쪽 부분에 2x2를 채울 수 있다(여기서 " ll "을 채우면 1번째 경우의 제일 오른쪽 " l "의 패턴과 같아지기 때문에 "="인 경우만 생각). 이 말은 무엇을 의미할까 ? 바로 직사각형의 제일 오른쪽 2칸은 이미 정해져 있다는 것을 의미한다. 4자리 숫자 순열에서 2자리가 이미 정해진 순열의 경우의 수는 (n-2)!가 된다. 그렇다면 위의 문제에서 (n-2)는 dp[n-2]다. 즉 n=2일때의 경우의 수.

 

그렇다면 왜 (n-3)은 안되는 것일까 ? 왜 이 문제의 풀이는 dp[n] = dp[n-1] + dp[n-2]로 접근해야 할까??

이것은 (n-1), (n-2)가 표현의 최소(?)이기 때문이다. 음..여기서 최소란 말은.. (n-3)은 (n-1), (n-2)로 "표현"할 수 있기 때문이다.  " l= ", " lll "," =l "은 1x2(n-1)와 2x2(n-2)로 표현할 수 있기 때문... 

 

사실 이해가 안갈 수 도 있지만...논리적으로 그렇게 돌아간다. 이해해야 하는 수 밖에 없다.

 

그리고 위의 논리가 증명되는 이유는 dp[n]에는 2xn 직사각형을 채울 수 있는 타일의 경우의 수를 넣는다고 우리가 약속했기 때문이다. 그렇기 때문에 처음에 dp[1]=1, dp[2]=2 라는 값을 넣어 주었다. 

 

어쨋든 개념은 이렇고, 문제를 풀면 된다. 숫자가 커질 수 있으니 배열에 저장할 때 %10007을 나눈 값을 저장하면된다.

#include <iostream>

using namespace std;

int main()
{

    int n;
    cin >> n;

    int dp[1001] = {0};
    dp[1] = 1;
    dp[2] = 2;

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

    cout << dp[n];

    return 0;
}