설탕 배달

문제

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

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

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

입력

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

출력

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

풀이

우리가 구해야 하는 것은 가장 적은 개수의 봉지이다. 단순히 생각하면 봉지의 개수를 가장 작게 해서 배달해야 하므로 배달해야 하는 설탕의 무게에서 5kg짜리가 얼마나 차지할 지 계산한 다음, 나머지 남은 무게만큼 3kg짜리를 챙기면 된다고 생각하기 쉽다.

하지만 예를 들어 6kg 설탕 배달을 해야 한다면, 5kg짜리 봉지의 개수를 먼저 계산하면 남은 1kg을 3kg짜리로 정확히 만들 수 없기 때문에 이 경우에는 3kg 짜리 봉지 개수를 먼저 계산해야 한다.

배달해야 하는 설탕의 무게를 봉지의 총 kg만큼 맞춰야 하므로 그렇다고 3kg짜리 봉지의 개수를 먼저 계산하는 것도 틀린 방법이다. 18kg 같은 경우에는 5kg과 3kg 짜리 봉지를 섞어서 배달할 수 있는데 3kg 짜리 봉지의 개수를 먼저 계산하면 배달할 때 가져가야 하는 최소 봉지 개수보다 더 많이 나오기 때문이다

그래서 이 문제에서의 핵심은 5kg짜리 봉지를 최대한 얼마나 많이 가져갈 수 있는지 계산하는 것이다. 위에서 언급했던 첫 번째 5kg 봉지가 얼마나 많이 필요한지 계산한 것에 추가해서, 5kg 봉지를 제외한 나머지를 3kg 봉지로 채울 수 있는지도 같이 계산해가며 5kg 봉지를 하나씩 줄여 나가는 방법이다.

즉 예를 들어 6kg 설탕을 배달해야 한다고 해보자. 그러면 우선 5kg 짜리 봉지를 최대한 많이 가져간다고 계산하면 1개의 봉지를 가져갈 수 있다. 이때 남은 kg은 1kg인데, 이는 3kg 설탕 봉지로 정확히 맞출 수 없는 양이다. 그러므로 여기서 5kg 봉지의 개수를 하나씩 줄여본다. 5kg 봉지가 0개일 때, 6kg에서 남은 설탕은 6kg이므로 이는 3kg 봉지로 정확히 맞출 수 있다.

이를 코드로 구현하면 아래와 같다.

kilogram = int(input())

big = int(kilogram / 5) // 5kg 봉지를 최대한 얼마나 많이 챙길 수 있는지
left = kilogram - (big * 5) // 5kg 봉지들을 제외한 남은 설탕의 용량이다

answer = -1

for i in range(big, -1, -1): // 5kg 짜리 봉지를 하나씩 줄여나가면서 계산한다.
    left = kilogram - (i * 5) // 5kg 봉지를 제외한 남은 용량

    if left % 3 == 0: // 남은 용량을 3kg 짜리로 정확히 채울 수 있는지 검사한다.
        answer = i + int(left / 3)
        break

print(answer)