백준 2839번 풀이

문제

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

2839번: 설탕 배달

설탕의 무게를 5킬로와 3킬로를 최소한으로 써서 나타내시오(…)

 

풀이

그러니까 이 문제를 간단히 요약하자면

5x+3y=z

x+y=w

여기서 z가 설탕의 무게(주어진다)일 때, 위 연립방정식을 만족하는 w의 최솟값을 찾는 문제. z가 주어지더라도 미지수가 세 개라서 방정식으로 풀면 안 된다. 연립방정식으로 풀 거면 w가 주어져야 하는데, 여기서는 z는 주어지지만 w는 주어지지 않는다. 즉, 일일이 대입해서 풀어야 한다… 어? 시간초과 각 아니냐? 그래서 찾아봤다…

 

Greedy 알고리즘은 대충 지금! 롸잇 나우! 제일 좋은 답! 을 도출해내는 알고리즘이다. 예를 들어보자면, 수중에 3000원이 있고 배가 고플 때, 편의점은 100m 걸어가야 있고 근처에 있는 타코야끼 트럭이 보인다. 하지만 편의점은 기다릴 필요 없이 3000원어치 사서 먹을 수 있고, 타코야끼 트럭은 줄이 길어서 10분정도 기다려야 할 것 같은 상황일 때, 최적의 선택은? 이런 거. 물론 실제로 저 선택에는 배고픔의 정도(10분 참을 수 있으면 타코야끼 각이지…), 3000원이 현금이냐 카드냐 등 여러가지 요인이 작용한다.

 

일단 Greedy 알고리즘에 대해 알아보기 전에 중요한 사실 한 가지를 전제하고 가자. 설탕 봉지는 온니 자연수다. -1봉지 0.5봉지 그런거 없다. 

 

Greedy 알고리즘의 예시로 많이 언급하는 게 ‘500, 100, 50, 10원짜리 동전을 최소한으로 써서 거스름돈을 주는 문제’이다. 예를 들어서, 두 개에 1980원 하는 오이를 네 개 사고 5000원을 냈을 때, 500, 100, 50, 10원짜리 동전으로 거스름돈(대략 1040원)을 주려면? 일단 500원짜리 두 개, 그리고 10원짜리 네 개를 주면 된다.

n = 1260
# 거스름돈
coin = [500,100,50,10]
# 동전
count = 0
for change in coin:
    count += n // change
    n = n % change
# 가장 큰 단위부터 계산한다
print(count)

그 예시가 이것. 참고로 저 코드의 답은 6. (500원 두개 100원 두개 하나하나) Greedy 알고리즘은 큰 값부터 한다길래

이 로직대로 했더니 망했다. 일부는 정상적으로 돌아가는데, 일부는 이상하게 나온다. 21이면 실제로 5가 답인데(5키로 3개, 3키로 2개) 7로 나온다거나… 

import sys
sugar = int(sys.stdin.readline())
pudae = 0
# 사실 Sucrose 하고 싶었음... (Sucrose=설탕, pudae=푸대)
while sugar >= 0:
    if sugar % 5 == 0:
        pudae += sugar // 5
        print(pudae)
        break
    sugar -= 3
    pudae += 1
else: 
    print(-1)

참고로 답은 이건데, 5로 나누어 떨어질때가지 3을 뺐다. 어? 나랑 순서가 반댄데? 근데 저거는 5의 배수가 될 때까지 빼고, 안 나눠지면 -1 하면 되는데 3의 배수로 나눠 떨어질때까지 5를 빼게 되면 처리할 게 너무 많아진다…