[Python 3] BOJ - 2839 "설탕 배달"
# 문제 링크 : https://www.acmicpc.net/problem/2839
2839번: 설탕 배달
문제 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다. 상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다. 예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬로그램 봉지 6개를 가져가도 되지만, 5킬로그램 3개와 3킬로그램 1개를 배달하면, 더 적은 개수의 봉지를 배달할 수
www.acmicpc.net
# 풀이 :
이 문제는 그래프를 그리면 쉽게 해결할 수 있다.
문제에서 배달해야하는 총 무게를 N이라 했고, 5kg짜리 봉지와 3kg짜리 봉지 2가지 종류가 있다. 따라서 각각의 종류의 쌍, (3kg x, 5kg y)에 대해 총 무게가 달리지므로 이것을 일차함수의 그래프로 나타낼 수 있다. 그러나, 부분만 채워갈 수 없기 때문에 x,y 모두 정수가 되는 경우만 세어야 한다. 따라서 x를 기준으로 지속적으로 x를 1씩 감소 시킬때, 그때의 y값을 편의상 몫만 취한다. 그 후 두점을 그래프에 대입하였을 때, 그래프 위에 존재한다면 즉, 총 무게 N을 만들 수 있다면 그 경우는 정답이 될 수 있는 후보가 되며, 그때의 x,y의 합이 가져가야 하는 봉지의 총 개수이다. 따라서 그때마다 정답의 최솟값을 갱신하면 최적해를 구할 수 있다.
# 코드
import sys
# 총 무게 입력
a = int(sys.stdin.readline())
# x절편과 y절편을 미리 구한다
three = a // 3
five = a // 5
ans = []
# 만일 N이 3과 5로 나누어 떨어지면 그때의 쌍을 정답배열에 저장한다
if a % 3 == 0:
ans.append((three , 0))
if a % 5 == 0:
ans.append((0, five))
# 지속적으로 x를 1씩 감소시킨다
while three > 0:
# temp = 그래프
temp = 3 * three + 5 * five
# 만일 (x, y)가 그래프 위에 있다면 정답배열에 추가
if temp == a:
ans.append((three, five))
# x, y좌표 갱신
three -= 1
five = (a - 3 * three) // 5
# 어떠한 경우도 봉지를 딱 떨어지게 가져갈 수 없는 경우
if len(ans) == 0:
print(-1)
# 최소값 변경
else:
res = 99999999999
for i in ans:
if res > sum(i):
res = sum(i)
print(res)