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

문제:

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

11727번: 2×n 타일링 2

 

풀이:

이 문제는 11726번 문제 '2 x n 타일링'에서 타일 하나를 더 추가한 문제이다.

2021.09.12 - [Python 코딩테스트] - DP(다이나믹 프로그래밍): 백준 11726 파이썬

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

 

11726번 문제와 마찬가지로 왼쪽부터 직사각형을 타일을 채운다고 생각하면 어렵지 않게 점화식을 세울 수 있다.

 

1. 왼쪽부터 i-1까지 길이가 타일로 이미 채워져 있으면 2 x 1의 직사각형을 채우는 하나의 경우 밖에

존재하지 않는다. 

2. 왼쪽부터 i-2까지 길이가 타일로 이미 채워져 있으면 1 x 2 타일 2개를 넣는 경우, 혹은 2 x 2의 타일 하나를 넣는 경우로 2가지 경우가 존재한다. 참고로 2 x 1 타일 2개를 넣는 경우를 고려하지 않는 이유는 1번에서 이미 해당 경우가 고려되었기 때문이다.

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

왼쪽부터 n -2까지 길이가 타일로 이미 채워져 있는 경우 직사각형을 채우는 방법은 2가지 경우가 있다.

이 두 방법은 서로 다른 것이므로, 결과적으로 a[i]는 a[i-1] + a[i-2] + a[i-2]가 된다. 

이를 코드로 옮기면 정답이 된다.

 

정답:

import sys

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

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])