[다이나믹 프로그래밍] 바닥 공사 - 파이썬(python)

바닥 공사

난이도 : 中下 풀이 시간 : 20분

시간 제한 : 1초 메모리 제한 : 128 MB

 

---

 

해답

 

n = int(input())

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

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

print(d[n])

---

예시

 

# 정수 N을 입력 받기
n = int(input())

# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [0] * 1001

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

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

---

해설

 

왼쪽부터 차례대로 바닥을 덮개로 채운다고 생각하면 점화식을 세울 수 있습니다.
1. i-1까지 채워져 있으면 2*1 덮개를 채우는 하나의 경우의 수
2. i-2까지 채워져 있으면 1*2 덮개 2개를 넣는 경우, 2*2 덮개 1개를 넣는 경우 총 2가지의 경우의 수
그러므로 점화식을 세워보면 a[i] = a[i-1] + a[i-2] + a[i-2]입니다.