[Python][백준] 2839_설탕 배달 (3가지 풀이방법)

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

2839번: 설탕 배달

문제

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

상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다. 예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬로그램 봉지 6개를 가져가도 되지만, 5킬로그램 3개와 3킬로그램 1개를 배달하면, 더 적은 개수의 봉지를 배달할 수 있다.

상근이가 설탕을 정확하게 N킬로그램 배달해야 할 때, 봉지 몇 개를 가져가면 되는지 그 수를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 N이 주어진다. (3 ≤ N ≤ 5000)

 

출력

상근이가 배달하는 봉지의 최소 개수를 출력한다. 만약, 정확하게 N킬로그램을 만들 수 없다면 -1을 출력한다.

 

* 풀이 1 : 수학

문제에서 3kg 봉지 개수를 X, 5kg 봉지 개수를 Y라고 하면

구하고자 하는 답 ans(최소값) = X+Y 이고, 3X+5Y = N을 만족한다. 이 식을 전개하면!

  : (2번식) Y = (N-3X) / 5 --> (1번식 대입) ans =  (2X+N) / 5

 

즉, 최소값 ans를 구하기 위해 (2X+N) / 5 가 나머지를 갖지 않도록 하는 가장 작은 X값을 구하면 된다.

--> for문으로 X값을 하나씩 증가시키자.

--> 단, 3X+5Y = N이므로 X <= N/3 이어야 한다.

x, ans = 0, -1
while x * 3 <= N:
    if (N + 2 * x) % 5 == 0 :
        ans = x + (N - 3 * x) / 5
        break
    x += 1

print(int(ans))

 

 

* 풀이2: 그리디 알고리즘

사용 봉지 갯수의 최소값을 구하기 위해 5kg 봉지를 최대한 많이 사용하는 것이 최적해이다.

(봉지 선택지가 3, 5kg 두가지밖에 없기 때문에 가능한 풀이이다.)

--> 1) N이하로 5kg 봉지를 최대한 많이 선택하고, 나머지 무게를 3kg 봉지로 채울 수 있는지 확인한다.

--> 2) 1이 불가능 하면 5kg 봉지를 1개 덜 사용하고, 3kg로 채울 수 있는지 확인한다.

--> 3) N이 채워졌을 때, 사용 봉지 갯수가 최적해가 된다.

N = int(input())
    ans = -1
    for i in range(N // 5, -1, -1):
        if (N - 5 * i) % 3 == 0:
            ans = i + (N - 5 * i) // 3
            break
    print(ans)

 

* 풀이3: 다이나믹프로그래밍(DP)

(봉지 선택지가 3개 이상으로 증가하면, 이 풀이방법이 셋 중에 유일하게 가능하다.)

답을 구하는 함수가 f(N)일 때, f(0)~f(5) = [0, -1, -1, 1, -1, 1] 이다.

ex) 6키로를 채우는 경우를 구해보면,

"3키로를 채울 때 필요한 최소 갯수" 과 "1키로를 채울 때 필요한 최소 갯수" 중에서 더 작은 값 + 1 이 답이된다.

식으로 나타내면 f(6) = min(f(6-3), f(6-5)) + 1 이다

 

--> f(n) = min(f(n-3), f(n-5)) + 1

--> 단, f(n-3), f(n-5)가 모두 -1이면 f(n)도 -1이다.

import sys
sys.setrecursionlimit(5000)

def dp(n):

    if n <= 5:
        return li[n]

    a = dp(n-5) if li[n-5] == sys.maxsize else li[n-5] 
    b = dp(n-3) if li[n-3] == sys.maxsize else li[n-3] 
    if(a==-1 and b==-1):
        li[n] = -1
        return -1
    elif(a==-1):
        li[n] = b+1
        return b+1
    else:
        li[n] = a+1
        return a+1

li = [sys.maxsize for _ in range(0,5001)]
li[0:6] = [0,-1, -1, 1, -1, 1]
N = int(input())

print(dp(N))

 

 

(두 명의 친구들과 이 문제를 같이 풀어봤는데 각각 다른 방법으로 풀어서 흥미 돋았던 문제)