[백준OJ] 2839번 설탕 배달

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

2839번: 설탕 배달

---

 

-풀이-

N kg을 배달해야 하는데 3키로와 5키로그램 봉지를 이용하여 가장 적은 봉지로 배달을 하기 위해선, 5kg 용량의 봉지를 이용하여 최대한 많이 담은다음, 나머지 설탕을 3kg 봉지를 이용하여 담으면 된다.

이때 3kg 봉지를 이용해서 담았을때, 남은 설탕이 있다면, 5kg 봉지를 하나씩 까면서 나온설탕들+남은 설탕들을 3kg봉지에 나누어 담으면 된다.

 

만약 5kg 봉지를 다시 다 깐 상태이고, 3kg봉지로 나누어 담았는데도 설탕이 남았다면, 5kg과 3kg으로 정확히 N kg을 만들 수 없게 된다는 의미이므로, -1을 출력한다.

 

-시간복잡도-

단순 계산식이므로 O(N)

 

-코드-

#include <algorithm>
#include<iostream>

using namespace std;


int main(){
    cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false);
    
    int n;
    int cnt5=0;
    int cnt3=0;
    cin>>n;
    cnt5=n/5;
    n%=5;
    
    while(true){
        if(n==0) break;
        
        cnt3+=n/3;
        n%=3;
        
        if(cnt5==0) break;
        
        if(n!=0){
            cnt5--;
            n+=5;
        }
    }
    if(n!=0){
        cout<<-1;
    }
    else{
        cout<<cnt5+cnt3;
    }
}