11726. 2 x n 타일링

 

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

11726번: 2×n 타일링

 

2 x n 크기의 직사각형을, 

1 x 2, 2 x 1 타일로 채울수 있는 방법의 수를 구하는 문제.

 

처음 풀어본 dp 문제인데 생각을 dp스럽게? 바꾸는게 어려운것 같다.

dp 문제는 점화식이 중요하기 때문에 다 풀고 보면 코드는 매우매우 간단한데 그 점화식 알아내기가 참 힘든것 같다.

많이 풀다 보면 딱 보면 어 이거 그문제랑 비슷한데? 이렇게 나온다는데 ..

 

 

일단 2 x n 크기의 타일이 있다고 생각해보자

이 2 x n 타일을 1 x 2, 2 x 1 로 채우는 방법의 수를 구해야하는데

처음에는 그냥 n = 1일때 부터 시작해서 n = 2일때 3일때 ... 쭉 구해서 풀었는데 그렇게 해도

풀리기는 한다. 근데 전혀 dp스럽지 않다.

이 문제는 풀릴지 몰라도 더 어려운 문제는 그런식으로는 안풀릴 것이다. 

 

일단

d[n] : 2 x n크기의 직사각형을 2 x 1, 1 x 2 타일로 구성 할 수 있는 총 방법의 수 

라고 하자

 

만약 2 x (n - 1) 까지 어떠한 방법으로든 채워져있다면 2 x 1 타일을 하나만 더 붙이면 2 x n 이 된다.

즉 d[n]은 d[n-1]의 가지수만큼 구할 수 있다.

 

 

또 2 x (n - 2)까지 어떠한 방법으로든 채워져있다면 1 x 2타일을 두개 붙이면 2 x n 이 된다.

즉 d[n]은 d[n-2]의 가지수 만큼도 구할 수 있다.

 

따라서 d[n]은 d[n-1]만큼 그리고 d[n-2]만큼도 구성할 수 있다. 따라서 점화식은

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

arr = [0] * 1001


def dp(a):
    if a <= 2: return a  # base check

    if arr[a] > 0: return arr[a]  # memoization

    arr[a] = dp(a - 2) + dp(a - 1)
    return arr[a]


n = int(input())  # 2 x n

for i in range(n + 1):
    arr[i] = dp(i)

print(arr[n] % 10007)

 

그렇다면 2 x (n-3)은 고려하지 않아도될까?

생각해보면 어처피 2 x (n - 1)에서 처럼 뒤에 2 x 1타일을 추가하거나

2 x (n - 2)에서 처럼 뒤에 1 x 2타일 두개를 추가한 것에서

2 x 1타일을 하나 추가한것이랑 같기 때문에 위에 두 케이스에 포함되있다고 할수 있다.

 

2 x (n - 4), 2 x (n - 5) ... 등등 마찬가지.