2839 설탕 배달 (python)

(2839) 설탕 배달

문제 🌐

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

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

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

입력

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

출력

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

접근 방법

가장 먼저, 봉지의 개수를 최소로 가져가겠다고 했으므로 웬만하면 5킬로그램 봉지를 최대한 가져가는 방향으로 생각해야 한다.

3과 5를 활용해 숫자를 만드는 경우의 수는 3가지가 있다.

1. N이 5의 배수인 경우: count = N//5 로 리턴할 수 있다
2. N이 5와 3의 조합으로 이루어진 경우 8 = 3 + 5 / 11 = 5 + 3 + 3 / 13 = 5 + 5 + 3
3. N이 3의 배수인 경우 이 경우, 5킬로그램 봉지를 사용하지 않고 3킬로그램 봉지를 사용하는 경우… N이 5의 배수가 아니면서, 5와 3의 조합으로 나올 수 없으며, 그저 3킬로그램 봉지로만 들고 가야 하는 경우… 9 = 3 + 3 + 3

▶ N이 5의 배수인가? > 맞으면 출력

① N이 5의 배수가 아닌 경우: 일단 3킬로그램 봉지를 하나 사용하고, 남은 설탕의 무게가 5의 배수인지 다시 확인한다.

② N = N-3 이 되고, 봉지의 개수 ++

③ ①로 돌아가서 다시 반복한다.

④ 만약 5와 3으로 만들 수 있는 숫자가 아니라면 결국 3보다 작은 정수 (1, 2) 가 남게 된다. 이 경우 -1을 출력

Full Solution

n = int(input())
count = 0

while n>0:
	# N이 5의 배수일 경우 출력
    if n%5 == 0:
        count += n//5
        break
	# N이 5와 3의 조합으로 만들 수 없는 숫자인 경우
    elif n==1 or n==2:
        count = -1
        break
	# 3킬로그램 봉지 +1
    else:
        n -= 3
        count += 1

print(count)