[Python 3] BOJ - 2839 "설탕 배달"

 # 문제 링크 : https://www.acmicpc.net/problem/2839

2839번: 설탕 배달

 

 # 풀이 :

이 문제는 그래프를 그리면 쉽게 해결할 수 있다. 

<그림 1. 3x + 5y = n>

 문제에서 배달해야하는 총 무게를 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)