Jin의 일상

문제설명

1. 설탕을 담을 수 있는 3kg짜리 봉투와  5kg짜리 봉투가 있다.

2. 설탕의 무게인 N이 주어졌을 때 사용할 최소의 봉투를 출력하자.

3. 정답이 없다면, -1을 출력한다.

문제 특이사항

- 반례로 N이 11인 상황을 예로 들 수 있습니다.

일반적인 풀이로는 5kg짜리 봉투가 가장 많을 때 답이 된다고 생각할 수 있습니다.

이런 경우에는 5kg짜리 봉투를 2개를 사용한 뒤에 나머지를 3kg짜리 봉투에 담아야 합니다.

그렇게 되면 3kg짜리 봉투에 들어갈 수 있는 설탕의 양은 2kg 밖에 되지 않습니다. 

즉, 문제에서 요구하는 답을 낼 수 없습니다.

5kg짜리 봉투 1개에만 적당히 소금을 담고,  3kg짜리 봉투를 2개를 사용하여 설탕을 담으면 문제에서 요구하는 정답을 제출할 수 있습니다.

알고리즘

N이 11로 주어진 상황을 가정하고 설명하겠습니다.

1. 5kg짜리 봉투가 허용하는 최대 무게부터 5 단위로 감소시키며, 0까지 반복문을 실행합니다.

2. N에서 5가 허용하는 무게(10, 5, 0)를 뺍니다.

뺀 값은 다시 N에 담습니다.

3. N을 3으로 나눕니다. 이 때 나머지가 0이면, 반복문을 빠져나옵니다.

4. 답으로는 5의 "'배수(2)'가 되는 값 + N/3의 몫"으로 제출합니다. (나머지가 0인 것이 없다면 -1을 답으로 제출합니다)

코드

import sys
# sys.stdin = open("C:/Users/JIn/PycharmProjects/coding_Test/input.txt", "rt")

inputData = int(input())
T = inputData//5
answer = -1
for i in range(T, -1, -1):
    n = inputData - (5 * i)
    a, b = divmod(n, 3)
    if b == 0:
        answer = i + a
        break
print(answer)