COCI 2010/2011 contest#7- 설탕 배달(secer) > 문제은행 : 정보올림피아드&알고리즘




2440 : 설탕 배달(secer)

제한시간
1000 ms   
메모리제한
32 MB   
해결횟수
2 회   
시도횟수
13 회   

문제

창재는 설탕공장의 배달사원이다. 설탕은 3kg 박스와 5kg 박스 두 종류가 있는데 이 두 종류를 이용하여 정확히 N kg 을 배달해야 한다. 그런데 창재는 N kg 의 설탕을 배달할 때 박스의 수를 가능한 적게 하고 싶어 한다.

예를 들어 18kg의 설탕을 배달하는 경우 3kg 설탕 6개를 배달할 수도 있지만 5kg 3박스와 3kg 1박스를 사용하는 경우 4박스만 배달하면 된다.

3kg 박스와 5kg 박스를 이용하여 정확히 N kg을 만드는데 필요한 최소 박스 수를 구하는 프로그램을 작성하시오.


입력형식

주문받은 설탕의 무게 N(3≤N≤50,000)이 입력된다.


출력형식

3kg 박스와 5kg 박스를 이용하여 정확히 N kg을 만드는데 필요한 최소 박스 수를 출력하시오.
정확히 N kg 을 만들 수 없는 경우 -1을 출력하시오.


입력 예

4

출력 예

-1

Hint!

입력 예 2
9

출력 예 2
3

입력 예 3
18

출력 예 3
4




경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP