백준(2839) - 설탕 배달 Python

백준(2839) - 설탕 배달

문제풀이 : 그리디 알고리즘, 파이썬

해결방법

문제 유형은 그리디지만, 다이나믹 프로그래밍 방식으로 해결했다.

n의 최대값이 5000이므로 5000까지 최대값으로 초기화 시킨후

3과 5 인덱스에 봉지 1개를 의미하는 1을 넣고,

n + 1까지 min(d[i], d[i-3] + 1, d[i-5]+1)을 순차적으로 저장해서 해결했다.

INF = int(1e9)
n = int(input())

d = [INF] * 5001
d[3] = 1
d[5] = 1
for i in range(3, n+1):
    d[i] = min(d[i], d[i-3] + 1, d[i-5]+1)

if d[n] == INF:
    print(-1)
else:
    print(d[n])