🔥

문제

북극곰 윌리는 요즘 콜라공장에서 콜라를 배달하고 있다. 윌리는 지금 콜라가게에 콜라를 정확하게 N병을 배달해야 한다. 콜라는 반드시 상자에 가득 담겨서 옮겨져야 하며, 상자는 콜라를 3병 담을 수 있는 상자와 5병 담을 수 있는 상자의 두 종류가 있다.

윌리는 상자가 많으면 배달하기 불편하기 때문에, 최대한 적은 수의 상자를 들고 가려고 한다. 예를 들어, 18병의 콜라를 배달해야 할 때, 3병이 든 상자를 6개를 가져가도 되지만, 5병이 든 상자 3개외 3병이 든 상자 1개를 배달하면, 총 4개의 상자로 더 적은 개수의 상자를 배달할 수 있다.

윌리가 콜라를 정확하게 N병 배달해야 할 때, 상자를 최소 몇 개 가져가면 되는지 그 수를 구하는 프로그램을 작성하시오.

입력

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

출력

윌리가 배달하는 상자의 최소 개수를 출력한다. 만약, 정확하게 N병을 만들 수 없다면 -1을 출력한다

예제 1 입력

18

예제 1 출력

4

예제 2 입력

6

예제 2 출력

2

Source

n = int(input())
ans = -1

for i in range(int(n/3) + 1):
	for j in range(int(n/5) + 1):
		total = i * 3 + j * 5
		if(total == n):
			box = i + j
			if(ans > box or ans == -1):
				ans = box

print(ans)

tip
j를 사용하는 대신 (n - 3 * i) % 5를 사용하여 두번째 for문을 지울 수 있다.

참고