DP(다이나믹 프로그래밍): 백준 11726 파이썬

문제:

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

11726번: 2×n 타일링

 

풀이:

이 문제는 다이나믹 프로그래밍의 기초 예제에서 빠질 수 없는 타일링 문제 유형이다. 다이나믹 프로그래밍 문제에서는 종종 결과를 어떤 수로 나눈 결과를 출력하라는 내용이 들어가 있는 경우가 많다.

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

 

왼쪽부터 차례대로 타일을 채운다고 생각하면 어렵지 않게 점화식을 세울 수 있다.

 

왼쪽부터 i-1까지 길이가 이미 채워져 있다면 남은 2 x 1 길이를 채우는 방법은 하나 밖에 존재하지 않는다.

 

왼쪽부터 i - 2까지 길이가 이미 채워져 있으면 1 x 2 타일 2개를 넣는 경우 하나가 존재한다.

참고로 2 x 1 타일 2개를 넣는 경우를 고려하지 않는 경우는 i-1이 채워져있는 경우에서 이미 해당 경우가 

고려되었기 때문이다. 

 

 

따라서 다음과 같이 점화식을 세울 수 있다. 

세운 점화식을 코드로 옮기면 정답이 된다.

 

정답:

import sys

n = int(sys.stdin.readline())

d = [0] * 1001

# 다이나믹 프로그래밍 진행 (보텀업)
d[1] = 1
d[2] = 2
for i in range(3, n+1):
    d[i] = (d[i-1] + d[i-2]) % 10007

# 계산된 결과 출력
print(d[n])