Notice
Recent Posts
Recent Comments
«   2024/11   »
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
Tags
more
Archives
Today
Total
관리 메뉴

No Limitation

[DP] 설탕 배달 - 백준 본문

프로그래밍

[DP] 설탕 배달 - 백준

yesungcho 2022. 2. 2. 18:46

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

 

2839번: 설탕 배달

상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그

www.acmicpc.net

 

다음 문제는 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))

'프로그래밍' 카테고리의 다른 글

[Greedy] 동전0 - 백준  (0) 2022.02.03
[DP] 평범한 배낭 - 백준  (0) 2022.02.03
[DP] N으로 표현 - 프로그래머스  (0) 2022.02.02
[DP] 동전 1 - 백준  (0) 2022.02.02
[DP] 정수 삼각형 - 프로그래머스  (0) 2022.02.02