백준/C++14 2839번 설탕 배달

https://www.acmicpc.net/problem/2839

2839번: 설탕 배달

코드

#include <iostream>
#include <string>
using namespace std;

int main()
{
    int n, sum = 0;
    cin >> n;

    while (n > 0)
    {
        if ((n % 5) % 3 == 0)
        {
            sum += n / 5;
            n %= 5;
            sum += n / 3;
            n %= 3;
        }
        else 
        {
            if (n - 3 < 0)
            {
                cout << -1;
                return 0;
            }
            n -= 3;
            sum++;
        }
    }

    cout << sum;

    return 0;
}

풀이

맨처음에는 아주 단순하게 접근했다가 틀렸다,,

요지는 결국 최소한의 총 봉투 수로 n을 나눠담아야 하는 것이기에 5kg 봉투를 최대로, 3kg 봉투를 최소한으로 가져가는 것을 목표로 한다.

로직은 다음과 같다. 

1. 5로 나눠지며 나눠진 수가 또 3으로 나눠진다면 바로 깔끔하게 5kg 봉투를 최대한으로 갖고 3kg 봉투를 최소한으로 갖는 봉투 수를 구할 수 있다.

2. 만약 위처럼 나눠지지 않는다면, 어쩔 수 없이 3kg 봉투를 하나 추가하고 ( n -= 3) 1번 분기로 돌아가 다시 테스트 해본다.

3. 계속해서 5kg봉투를 최대한 많이 쓰는 방향으로 루프를 돌리지만, 만약 n -= 3을 계속 했는데도 1번 분기를 만족하지 않고 음수가 나온다면 이는 5kg 봉투와 3kg 봉투로 나눠담을 수 없는 n이기에 -1을 출력한다.