2839: 설탕 배달

• toc {:toc}

문제 확인하기

풀이

그리디 알고리즘을 사용하는 문제로, 최소 개수의 봉지를 배달해줘야 하기 때문에 5로 먼저 나누고 3으로 나눌 수 있는지를 확인한다. 큰 수로 나누는 것이 아니라 5로 나누는 것이기 때문에 1, 2, 3, 4일 때의 테스트 케이스를 나누어 진행했다.

예를 들면 6 이 입력으로 들어온 경우 5로 나누어 나머지가 1이 나오고 이 때, 3으로 나눌 수 없기 때문에 5로 나눈 몫을 1 줄이고 3으로 나눠준다. 이런 식으로 케이스를 나누어 생각했다.

#include <bits/stdc++.h>
using namespace std;
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
 
    int N, temp, five, three = 0;
 
    cin >> N;
 
    temp = N;
 
    five = N / 5;
    N = N % 5;
 
    if(temp == 4 || temp == 7){
        cout << -1 << '\n';
        exit(0);
    }
    if(N == 1){
        five -= 1;
        three = 2;
    }
    else if(N == 2){
        five -= 2;
        three = 4;
    }
    else if(N == 3){
        three = 1;
    }
    else if(N == 4){
        five -= 1;
        three = 3;
    }
 
    cout << five+three << '\n';
    
 
    return 0;
}

위 풀이는 단순히 케이스를 나눠서 푼 풀이였지만, 케이스가 많은 경우에는 일일이 나눌 수 없다. 때문에 반복문을 이용해서 풀이하는 방법도 있다. 결국 우리는 최대한 많은 개수의 5kg 설탕 봉지를 제공해야 한다. 때문에 전체를 5로 나누었을 때 딱 떨어지는 경우가 최대한 5kg으로 제공할 수 있는 방법이다. 만약, 5로 나누었을 때 딱 떨어지지 않는다면, 3kg으로 제공하는 방법밖에 없기 때문에 전체에서 3을 1회씩 빼주고 5로 나누는 과정을 반복한다.

#include <iostream>
 
using namespace std;
 
int N;
int main() {
	cin >> N;
	int ans = 0;
	while (N>=0) {
		if (N % 5 == 0) {	//가장 큰 수로 나누는게 가장 작은수랑 섞어서 나누는 것보다 유리
			ans += (N / 5);	//나눈 몫을 더한 것이 정답
			cout << ans << endl;
			return 0;
		}
		N -= 3;	//3kg을 빼고 
		ans++;	//가방 하나 늘어남
	}
	cout << -1 << endl;
}