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

바닥 공사

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

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

 

---

 

해답

 

n = int(input())

dp_table = [0] * 1001

dp_table[1] = 1
dp_table[2] = 3

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

print(dp_table[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. 가로의 길이가 n-1 크기만큼 채워진 경우, 2x1 덮개 하나로만 채울 수 있습니다.
2. 가로의 길이가 n-2 크기만큼 채워진 경우, 1x2 덮개 2개를 넣는 경우와 2x2 덮개 1개를 넣는 경우 총 2개의 경우가 생깁니다.
dp 테이블의 1과 2번째 초기값을 설정해주고, 점화식을 활용하여 for 반복문을 돌려주었습니다.