설탕공장 문제

프로그램 명: sugar

제한시간: 1 초

미코는 설탕공장의 배달원이다.

이 공장에는 3 , 5 킬로그램 두 가지 종류의 설탕 포대가 있다.

주문량이 주어질 경우 가장 최소의 설탕 포대로 배달하게 미코를 도와 주는 것이다.

입력

주문 량 N 이 입력으로 주어진다. N (3 ≤ N ≤ 5000).

출력

최소 포대 수를 출력하고 가능하지 않는 경우에는 -1 을 출력한다.

입출력 예

입력

4

출력

-1

입력

9

출력

3

입력

18

출력

4

출처:coci 2011 contest7 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>
 
using namespace std;
 
int main()
{
    // 1. 3킬로, 5킬로 포대가 있다.
    // 2. 5킬로 포대로만 모두 담을 수 있다면 가장 적은 포대수 가 나온다.
    // 3. 5킬로 포대수로 최대한 담아본다.
    // 4. 5킬로 포대를 하나씩 줄여가며 3킬로 포대로 나누어 떨어지는 순간을 기다린다.
    // 5. 5킬로 포대가 한개도 없어도 3킬로 포대로 나누어 떨어지지 않는다면 -1을 출력
 
    int N;
    
    cin >> N;
 
    int F = N/5;
 
    if(N%5==0){
        cout << F << endl;
        return 0;
    }
    else{
        while(F>=0)
        {
            if((N - (5*F)) % 3 == 0) break;
            else F--;
        }
    }
 
    if(F<0) cout << -1 << endl;
    else cout << F + ((N - (5*F)) / 3) << endl;
}