[11726] 2×n 타일링

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

11726번: 2×n 타일링

<문제>

가장 왼쪽 위 타일을 채우도록 배치한다고 생각해보자.

이후, 최소 크기의 2*x의 직사각형을 만드는 경우의 수가 k라고 할때

dp[i] = k * dp[i-x]의 점화식이 생성된다고 생각하는 방식으로 접근하면 보다 쉽다.

 

 

첫번째로는, 가로로 눕혀서 가장 왼쪽 위 타일을 채우는 경우가 있겠다.

같은 방식으로 가장 왼쪽 아래에 가로로 타일을 추가적으로 배치한다면

2개의 가로로 된 타일로, 2*2의 직사각형을 만들 수 있다

이때, 이미 채워진 타일의 오른쪽에는 타일을 더이상 배치하지 않아야 한다(최소단위를 만족하지 않음)

현재에는 x=2, k=1인 셈이므로 dp[i] = dp[i-2]의 점화식이 나온 셈이다.

 

두번째로는, 가장 왼쪽에 세로로 블럭을 배치하는 경우가 있다.

이 경우에는, 그 자체로 1*2의 직사각형이 생성되었고, 이것이 당연히 최소단위가 되므로

x=1, k=1으로 dp[i] = dp[i-1]의 점화식이 생성되었다.

 

이를 종합하여 생성된 점화식은 dp[i] = dp[i-2] + dp[i-1]

피보나치와 동일한 형태의 점화식이 유도된것을 볼 수 있다.

<소스코드>

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