1. 문제

출처: 백준 2839번 설탕 배달

2. 풀이

설탕 5킬로그램 봉지가 더 큰 단위기 때문에, 최대한 챙기는 것이 개수를 줄이는 데 도움이 된다.

5킬로그램 봉지로만 배달한다고 했을 때 최대 개수를 올림으로 구한다.
그리고 하나씩 줄여나가면서 나머지 무게를 3킬로그램 봉지로 맞출 수 있는지 확인한다.

한 편, 3킬로그램 봉지로만 배달한다고 했을 때 최대 개수를 올림으로 구한다.
그리고 1개부터 최대 개수까지 3킬로그램 봉지의 개수를 늘려가면서, 나머지 무게를 5킬로그램 봉지로 맞출 수 있는지 확인한다.

위의 두 가지 방식으로 구한 개수를 비교하여 작은 값을 출력하고, 만약 딱 떨어지는 무게를 만들 수 없다면 -1을 출력한다.

3. 소스코드

N = int(input())

max_num_5 = N//5+1
max_num_3 = N//3+1
num = -1

for i in range(max_num_5,-1,-1):
    weight_5 = 5*i
    num_3 = (N-weight_5)//3
    if num_3 < 0:
        num_3 = 0
    if (weight_5+num_3*3 == N):
        num = i+num_3
        break

for j in range(1,max_num_3):
    weight_3 = 3*j
    num_5 = (N-weight_3)//5
    if num_5 < 0:
        num_5 = 0
    if (weight_3+num_5*5 == N):
        if num ==-1:
            num = j+num_5
            break
        elif num !=-1 and num>j+num_5:
            num = j+num_5
            break

print(num)

4. 그 외

딱 떨어져야한다는 조건 때문에, 그리디 알고리즘 적용이 안 되었던 것 같다.