백준 2839번 (C++)

www.acmicpc.net/problem/2839

2839번: 설탕 배달

 

<답안>

#include <iostream>

using namespace std;

int main() {

    int n;

    int count3 = 0, count5 = 0;

    int rest;

    bool find = false;

    cin>>n;

    

    count5 = n/5;

    rest = n%5;

    if(rest == 0)

        cout<<count5;

    else

    {

        while(!find)

        {

            if(count5<0)

            {

                cout<<-1;

                find = true;

            }

            else if(rest%3 == 0)

            {

                count3 = rest/3;

                cout<<count5+count3;

                find = true;

            }

            else

            {

                count5--;

                rest+=5;

            }

        }

    }

    return 0;

}

<설명>

문제보자마자 알고리즘이 떠오르진 않았다 지인의 아이디어 덕분에 열쇠가 풀렸었다

5가 3보다 크기 때문에 입력된 n을 먼저 5로 나누어 몫 count5를 구한다

그리고 5로나눈 나머지 값을 rest로 저장한다

 

만약 rest값이 3으로 나눠지는 경우 정답인 케이스 이므로

rest/3 값을 count3에 저장한 다음 count5 + count3를 출력하면 된다

 

만약 3으로 나눠지지 않는 경우 count5를 1 감소시키며 rest값을 5를 더한다

그리고서 다시 비교를 반복하여 count3값을 찾으면 된다

 

만약 count5가 0인데도 count3값이 구해지지 않는 경우는

3과 5의 조합으로 만들 수 없는 숫자이다

그런경우 -1을 출력하면 된다