[BOJ] 백준 11727번 - 2xn 타일링 2 (Python)

문제

문제 바로가기

해결

DP문제의 대표적 예시인 타일링 문제 유형이다.

DP는 무조건 작은 문제들로 쪼개서 쪼갠 문제들 몇개로 큰 문제 점화식으로 나타낼 수 있어야 한다. 즉, DP테이블에서 작은 문제 몇 개를 뽑아서 지금의 문제를 풀 수 있어야 한다.

DP 테이블의 기초값은 다음과 같다.

• 2*1 길이의 타일에는 1개의 경우가 존재한다.

• 2*2 길이의 타일에는 3개의 경우가 존재한다.

그리고 이 문제의 점화식은 다음과 같다.

• 2*i길이의 타일의 경우 = (2*(i-1))길이의 타일의 경우 + (2*(i-2))길이의 타일의 경우 x 2

즉, ai = a(i-1) + 2 * a(i-2)와 같다.

이를 파이썬으로 나타내면 다음과 같다.

n = int(input())

d = [0] * 1001
d[1] = 1
d[2] = 3

for i in range(3, n+1):
    d[i] = (d[i - 1] + d[i - 2] * 2) % 10007

print(d[n])

이 문제에서는 `10,007로 나눈 나머지를 출력하라고 하는데, 이는 단지 결괏값이 굉장히 커질 수 있기 때문에 그런 것이다. 따라서 값을 계산할 때마다 특정한 수로 나눈 나머지만 취하면 된다.