[PS 백준 - 3.2] 2839번: 설탕 배달

문제 정보

백준 2839번 - 바로가기

• 난이도: 브론즈 1
• 알고리즘: 그리디 알고리즘

---

코멘트

이전의 거스름돈 문제와 비슷한 문제지만 조금 더 함정이 있었다. 큰 것부터 없애고 싶어서 5 단위로 5 미만이 될때까지 자르고 3 단위로 자르면 답이 제대로 안나온다.

따라서 브루트포스처럼 3이 0개 있을 때, 1개 있을 때, ... 이렇게 모든 과정을 탐색하도록 코드를 짰다.

---

소스 코드

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    
    int x;
    cin >> x;
    int cnt = 0;

    int min = x / 3 + 1;

    vector<int> bongs;
    
    for (int i = 0; i < min; i++) {
        int y = x;
        int cnt = 0;

        y -= 3 * i;
        cnt += i;

        if (y % 5 == 0) {
            cnt += y / 5;
            bongs.push_back(cnt);
        } 
    }

    sort(bongs.begin(), bongs.end());
    // for (auto it = bongs.begin(); it != bongs.end(); it++) 
    // 	cout << *it << ' ';
    
    if (bongs.size() != 0)  cout << bongs.front();
    else cout << -1;
}