백준 2839번: 설탕 배달 (python, 파이썬)

• 문제

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

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

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

---

• 입력

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

---

• 출력

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

---

• 코드

n = int(input())

three = 0 # 3kg 설탕
five = 0  # 5kg 설탕

# 5로 나눈 몫을 먼저 계산
while((n // 5) != 0):
    five += 1
    n -= 5

# 0이 되기 전까지 반복문
while(n != 0):
    if five == -1:
        break
    # 4, 7일때 예외 계산
    if (five == 0 and n == 4) and (five == 1 and n == 2):
        five = -1
    # 3으로 나눈 나머지가 0일때
    elif n % 3 == 0:
        three += 1
        n -= 3
    # 3으로 나눈 나머지가 0이 아닐때
    elif n % 3 != 0:
        five -= 1
        n += 5

answer = three + five
print(answer)

설탕 배달 문제는 greedy 알고리즘이다. 간단히 말해서 욕심을 부린다는 뜻인데 일단 최적의 방향을 먼저 생각한다는 뜻이다. 

이 문제에서는 봉지를 최소한으로 가져가야 하기 때문에 일단 5kg짜리 설탕을 가능한 먼저 가져가는 것이다.

13kg 처럼 5+5+3이렇게 떨어지면 문제가 정말 쉽겠지만 16kg을 생각해보면 5+5+5를해서 일단 담게되면 1kg이 남아 설탕 배달이 불가능하다.

 

그러나 좀만 생각해보면 문제는 되게 간단하다. 원리는 5kg을 일단 담고 이후에 3kg으로 처리가 불가능할땐 다시 이전으로 되돌려서 3kg으로 배달이 가능할때로 돌아가면 되는 것이다. 위의 코드는 복잡하게 작성했지만 곰곰히 살펴보니 매우 간단하게 줄일 수 있는 방법을 찾았다.

n = int(input())
answer = 0
while n % 5:
    n -= 3
    answer += 1
print(-1 if n < 0 else (n // 5) + answer)

5로 나누어 떨어지지 않으면 3으로 미리 계산을 해주고 남은 n에서 5를 나누어 몫으로 생각해주면 된다.

---

• 출처

www.acmicpc.net/problem/2839