[백준] 다이나믹 프로그래밍 2839 설탕 배달

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

 

import sys

N = int(input())

count = 0

d = [-1] * (5001)


d[3] = 1
d[5] = 1
for i in range(6,N+1):
    if i % 5 == 0:
        d[i] = d[i-5] + 1
    elif i % 3 == 0:
        d[i] = d[i-3] + 1
    elif d[i-3] > 0 and d[i-5] > 0:
        d[i] = min(d[i-3],d[i-5]) + 1




print(d[N])

1. 3kg , 5kg는 자기 자신 한개가 전부이므로 , d[3] = d[5] = 1로 초기값 세팅 가능

5 이하의 숫자들은 더이상 만들 수 없으므로 , 반복문은 6부터 시작 -> 시간복잡도 : O(N)

만약 5 , 3으로 나누어 떨어진다면 일단 d[i] = d[i-5] + 1, d[i] = d[i-3] + 1로 갱신,

하지만 21같은 수는 3x7보다 , 5x3 + 3x2로 7 > 5이므로, 마지막으로 비교가 필요하다

8같은 수는, 5x1 + 3x1로 구성 가능

이때 d[5] , d[3] > 0 이므로 d[8] = 1 + 1 = 2 

둘중 작은 값을 선택하고 , 한개를 더 추가한다는 느낌으로 생각하면 될 것 같다

마지막줄 떠올리는게 조금 쉽지 않았음.