[백준 11726, 11727] 2XN 타일링 (DP, 점화식)

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

11726번: 2×n 타일링

 

DP 알고리즘을 사용해서 푸는 문제라는 것은 알고있었지만, 문제를 봐도 어디서 DP를 사용해야하는지 모르겠었다.

그래서 내가 찾았던 나름대로의 규칙(조합을 이용하여 풀었다. dp[i] = (i/2+i%2)C(i/2) + ... + i-1C1 + iC0) 을 통해 값을 구하려했지만, 정수범위 내에서 계산하기에는 범위가 너무 커져서 결국 런타임에러로 문제를 풀지 못했다.

휴 DP어렵다..ㅠ

 

2XN 타일을 채울 때, N이 1, 2, 3, 4 인 경우를 그림을 통해 조합의 가짓수를 나타냈다.

이때, N이 3, 4 인 경우 가장 오른쪽 타일을 분리시켜 다시 나타낸 경우를 파란색으로 그렸다.

 

파란색그림을 통해, 타일을 채워넣는 경우는 (1)맨 오른쪽이 2X1 타일이거나 / (2)맨 오른쪽이 2X2 타일인 두가지 경우로 나눌 수 있고

전체 방법의 수는 맨 오른쪽에 2X1 타일과 2X2 타일을 고정시키고난 나머지 타일을 채우는 방법의 수( (1)일때 나머지는 n-1개, (2)일때 나머지는 n-2개)임을 알 수 있다.

 

이를 일반화 시켜보면, 2XN 타일을 채우는 경우 아래의 그림과 같이 표현할 수 있다.

2XN 타일을 채우는 방법의 수를 dp[n] 타일에 각각 저장한다고 하면,

오른쪽 타일을 고정시키고 남은 타일인 n-1의 조합 가짓수와 n-2의 조합 가짓수는 dp[n-1]과 dp[n-2]로 표현될 수 있으므로

dp[n] = dp[n-1] + dp[n-2]

라는 점화식을 도출해낼 수 있다!

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
 
int main() {
    int n;
    int dp[1001] = { 0, };
    scanf("%d", &n);
 
    dp[1] = 1;
    dp[2] = 2;
    for (int i = 3; i < n+1; i++) {
        dp[i] = (dp[i - 1] + dp[i - 2])%10007;
        
    }
    printf("%d", dp[n]);
 
    return 0;
}

---

(+) 11727번 또한 11726번 문제와 동일하게 풀이할 수 있다.