2839 - 설탕배달

 

---

 

문제 (S4)

 

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

2839번: 설탕 배달

 

풀이

 

DP 연습이 필요할 거 같아서, 실버문제들을 쭈욱 풀면서 감을 잡으려 한다.

 

설탕배달은 단순하다. D[n]은 n Kg 을 배달하는 최소 설탕봉지의 개수가 저장되어 있다.

 

초기값으로 D[3] = 1 , D[5] = 1 로 설정해준다.

그리고 6부터 loop를 돌려준다.

 

이 때 n kg 일때, d[n-3] 또는 d[n-5] 값이 있다면 해당값으로 갱신해준다. 

만약 d[n-3], d[n-5] 값 중 하나만 있다면 그 값 + 1 로 갱신해주고

아니라면 둘 중 최솟값을 찾아서 + 1 해준다.

 

코드

d = [-1] * 5001
d[3] = 1
d[5] = 1

n = int(input())

for i in range(5001):
    if i < 6: continue

    if d[i-3] == -1 and d[i-5] == -1:
        d[i] = -1

    elif d[i-5] == -1:
        d[i] = d[i-3]+1
    elif d[i-3] == -1:
        d[i] = d[i-5] + 1
    else:
        d[i] = min(d[i-3], d[i-5]) + 1

print(d[n])