백준 2839번 풀이 (파이썬) - DP / 그리디 알고리즘

 

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

2839번: 설탕 배달

 

문제 설명

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

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

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

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

 

 

 

 

나의 풀이

N = int(input())

five = N // 5 + 1
three = N // 3 + 1
result = 0
end_point = False

for i in range(five + 1):
  if end_point == True:
    break
  for j in range(three):
    if N == (((five-i) * 5) + (j * 3)):
      result = (five - i) + j
      end_point = True
      break

if result == 0:
  result = -1
  
print(result)

five와 three는 각각 5킬로그램 봉지와 3킬로그램 봉지의 최대 개수 + 1 이다

5킬로그램 봉지 개수가 five 이하이고, 3킬로그램 봉지 개수가 three 이하일 때,

정확히 N킬로그램을 표현하는 경우 중, 5킬로그램 봉지 개수가 가장 큰 경우를 찾는 알고리즘을 작성했다.

 

그리디 문제로 인식했으나, 풀이는 그리디 알고리즘을 사용했다고 보기가 좀 그렇다.

찾아보니 아직 안 배운 동적 프로그래밍(DP)에 가까운 것 같다.

 

 

 

남의 풀이

def sugar_bag(N):
    bag_3 = 0
    bag_5 = N // 5
    r = N % 5
    while (bag_5 >= 0):
        if r % 3 == 0:
            bag_3 = r // 3
            return bag_3 + bag_5
        bag_5 -= 1
        r += 5
    return -1
    
    
N = int(input())
print(sugar_bag(N))

3킬로그램, 5킬로그램 봉지 개수를 각각 bag_3, bag_5로 정의한다.

N을 5로 나누고 나눈 나머지를 r로 정의한다.

 

r을 3으로 나눴을 때,

나누어 떨어진다면 바로 bag_3, bag_5의 합을 반환한다.

나누어 떨어지지 않는다면 나머지에 5를 더하고 bag_5을 한 개 빼준다.

 

 

확실히 그리디 알고리즘을 사용한 풀이다.

3과 5의 최소공배수인 15에 대해,

5킬로그램 봉지 3개를 사용하는 것이 무조건 이득이므로

그리디 알고리즘 사용 형태에 해당한다.

 

 

 

 

참고 자료 : https://www.acmicpc.net/source/17359883