[beakjoon-2839-C++] 설탕 배달

문제

상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다.

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

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

입력

첫째 줄에 N이 주어진다. (3 ≤ N ≤ 5000)

출력

상근이가 배달하는 봉지의 최소 개수를 출력한다. 만약, 정확하게 N킬로그램을 만들 수 없다면 -1을 출력한다.

코드

#include <iostream>
using namespace std;

int main(){
	int n, min, fiv, thr;
	cin >> n;
	min = -1;
	fiv = n / 5;
	for (int i = 0; i <= fiv; i++) {
		thr = (n - i * 5) % 3;
		if (thr == 0) {
			if (min > i + (n - i * 5) / 3 || min == -1) {
				min = i + (n - i * 5) / 3;
			}
		}
	}
	cout << min;
}

간단하게 생각했을 때, 제일 적은 봉지 개수를 구하기 위해서는 n을 5로 나누고 나머지를 3으로 나누면 된다.

다만 이때, 5로 나누었을 때의 나머지가 3의 배수가 아닐 경우, 오답이 나오게 되는 문제가 발생한다.

이를 해결하기 위해, n을 5로 나누어 범위를 지정하고 5kg짜리 설탕 봉지의 개수 별로 3kg짜리 설탕 봉지가 몇 개 필요한 지 구하여 최솟값을 구하였다.

다른 사람의 코드

#include<stdio.h>
int main(){
	int n,i=0;scanf("%d",&n);
    while((n-3*i)%5){
    	i++;
        if(3*i>n){
        	printf("-1");
            return 0;
        }
    }
    printf("%d",(n-3*i)/5+i);}
    
    //https://www.acmicpc.net/source/38974684

n에서 3kg 짜리 봉지개수를 뺀 나머지가 5로 나누어 떨어지는 지 확인함으로써 최소 개수를 구하는 방식입니다.

이 때 3kg짜리 봉지의 무게가 n을 넘어가게 되면 -1을 출력하고 함수를 종료하게 하였습니다.

최솟값을 구하고 난 이후의 필요없는 연산을 하지 않으므로 수행 시간이 더 줄어들었습니다.