[DP] 설탕 배달 - 백준

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

2839번: 설탕 배달

 

다음 문제는 Dynamic Programming으로 푸는 문제인지는 잘 모르겠지만

 

여기서는 단위 3, 5를 기반으로 푸는 것이라는 아이디어는 DP에 기초함

 

예를 들면 다음을 생각해보자

 

18을 만들어야 하는데

3, 5단위로 만들려면

3을 6번 쓸 때

5번 쓸 때,...

이럴 때 5로는 어떻게 만들고

이런 경우의 수를 계산해주면 문제는 간단히 구현된다

 

N = int(input())

i = 1
while 3*i < N :
    i += 1

j = 0; sum_list = []
for k in range(i, -1, -1) :
    if k == 0 :
        if N%5 == 0 :
            sum_list.append(N//5)
    elif N%(3*k) == 0 :
        if 3*k == N :
            sum_list.append(k)
        elif (N - (3*k))%5 == 0 :
            sum_list.append(k + (N-(3*k))//5)

    else :
        if (N-(3*k))%5 == 0 :
            sum_list.append(k + (N-(3*k))//5)
            
if sum_list == [] :
    print(-1)
else :
    print(min(sum_list))