백준 2839 - 설탕 배달

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

2839번: 설탕 배달

문제 설명

---

상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 설탕을 정확하게 N킬로그램을 배달해야 한다.

봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다. 최대한 적은 봉지를 들고 가려고 한다.

예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬로그램 봉지 6개를 가져가도 되지만, 5킬로그램 3개와 3킬로그램 1개를 배달하면, 더 적은 개수의 봉지를 배달할 수 있다.상근이가 설탕을 정확하게 N킬로그램 배달해야 할 때, 봉지 몇 개를 가져가면 되는지 그 수 구하시오!

 

 

접근 방식

---

가장 큰 봉지를 최대 n개를 들고갈 수 있다고 가정할때, 0부터 n까지 경우마다 3kg의 봉지를 들수 있는 경우를 구해서 백터에 저장한다.

그 다음 정럴후에 가장 작은 백터의 요소를 구하면 된다.

 

 

코드

---

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

using namespace std;
int n;
int main(){
    cin>>n;
    int big_s=5;
    int small_s=3;
    vector<int>ans;
    for(int i=0;i<=(n/big_s);i++){
        if((n-i*big_s)%small_s==0){
            ans.push_back((i+(n-i*big_s)/small_s));
        }
    }
    if(ans.size()==0) cout<<-1<<"\n";
    else{
        sort(ans.begin(),ans.end());
        cout<<ans[0]<<"\n";
    }
    return 0;
}

funny algorithms *0* ~