백준 11727번 2×n 타일링 2 파이썬 풀이

Python

[Python] 백준 알고리즘 온라인 저지 11727 2×n 타일링 2

11727 2 x n 타일링 2

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

11727번: 2×n 타일링 2

11726번의 후속 문제로 2x2타일이 추가되었다. 풀이 방법은 11726번 2×n 타일링 파이썬 풀이과 동일하게 동적 계획법과 점화식을 이용하여 풀이하였습니다.

---

코드

import sys
input = sys.stdin.readline

n = int(input())
dp = [0, 1, 3, 5]

for i in range(4, n+1):
    dp.append((dp[i-1] + (dp[i-2] * 2)) % 10007)

print(dp[n])

---

풀이

점화식을 세우기위해 작은 수의 n들을 먼저 계산해줍니다. 미리 계산한 내용들 n[0, 1, 2, 3] = [0, 1, 3, 5]을 dp로 선언하고 이를 활용한 점화식은 dp(n) = (dp(n-1) + (dp(n-2) * 2)) 즉 dp = dp[n-1] + (dp[n-2] * 2)의 점화식이 만들어진다.

for문을 활용해 작성되지않은 dp 4번째부터 순서대로 계산해 나가도록 코드를 작성합니다. 조건과 같이 10007을 나누고 n번째 dp를 출력해주면 됩니다.

---

풀이 결과

11727 2 x n 타일링 2