[BOJ] 2839_설탕 배달

문제
N킬로그램을 배달해야 하는데, 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다. 최대한 적은 봉지를 들고 가려고 한다.
예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬로그램 봉지 6개를 가져가도 되지만, 5킬로그램 3개와 3킬로그램 1개를 배달하면, 더 적은 개수의 봉지를 배달할 수 있다.

상근이가 설탕을 정확하게 N킬로그램 배달해야 할 때, 봉지 몇 개를 가져가면 되는지 그 수를 구하는 프로그램을 작성하시오.

---

풀이
언뜻 간단해보이지만 까다로운 예시가 많은 문제다. 무조건 5로 최대한 나누고 나머지 3으로 메꾸면 될 것 같지만, 11kg 일 경우 5kg 1개에 3kg 2개가 될 수도 있다는 것들을 고려해야한다.

📌 최대한 적은 봉지를 들고 가려고 하지만, 우리는 Nkg 을 전부 옮기려는 게 우선이라는 걸 잊어선 안된다.

이것만 알면 풀이는 간단해진다. 일단, 봉지를 나누는데 우선순위를 생각해보자. 할 수 있는 한 5kg 봉지에 최대한 담는 게 중요하다. 그렇기에 알고리즘은 이러하다.

1. 5kg 으로 전부 나뉘는가?
2. 5kg, 3kg 으로 전부 나뉘는가?
   2-1. 5kg 봉지를 1개씩 줄이고, 3kg 봉지를 1개씩 늘리는 과정을 반복한다. (5kg, 3kg 으로 딱 나뉘는 순간 반복은 멈춘다. / 과정은 3kg 봉지 전부를 사용해볼 때까지 반복한다.)
   2-2. 위 과정에서 멈추지 않을 시 나뉘지 않는 것이므로 "-1" 출력.

---

풀이 코드

#include<iostream>
using namespace std;

int main(void){

    cin.tie(NULL); ios_base::sync_with_stdio(false);

    int sugar;
    cin>>sugar;

    if(sugar%5==0){
        cout<<sugar/5;
    }
    else{
        for(int i=sugar/5;i>=0;i--){
            if((sugar-5*i)%3==0){
                cout<<i+(sugar-5*i)/3;
                return 0;
            }
        }
        cout<<"-1";
    }
}

---

문제 출처 : https://www.acmicpc.net/problem/2839