백준 2839 - 설탕 배달 ( C++ / Java )

 

---

문제 풀이 

 

그리디 알고리즘을 적용하여 해결 가능합니다.

 

봉지가 담을 수 있는 무게는 3kg와 5kg 두개이고 설탕의 최대무게는 N이다.

 

3kg 봉지와 5kg 봉지로 무게 N을 맞출 수 있는 조합을 모두 구한 뒤

 

3kg 봉지 개수와 5 kg 봉지 개수의 합이 가장 작은 것을 찾아 출력하면 됩니다. 

 

3kg 봉지와 5kg 봉지의 조합은 반복문으로 찾을 수 있습니다.

 

---

코드

Java

import java.util.Scanner;
 
public class Main {
    public static void main(String [] args) {
 
        Scanner sc = new Scanner(System.in);
 
        int n;
        n = sc.nextInt();
 
        int minTotalBags = 5000;
 
        for ( int i = 0 ; i <= n / 3 ; i++ ) {
            int temp = 0;
            temp += i;
            if ( ( n - i*3) % 5 == 0 ) {
                int fiveKiloBagNum = ( n - i * 3 ) / 5;
                temp += fiveKiloBagNum;
                if ( minTotalBags > temp )  minTotalBags = temp;
            }
        }
        if ( minTotalBags == 5000 ) {
            System.out.print(-1);
            return ;
        }
        System.out.print(minTotalBags);
    }
}
 
 

 

C++

#include <iostream>
 
using namespace std;
 
int main (void) {
 
    int n;
    const int MAX = 5000;
    cin >> n;
 
    int minTotalBags = MAX;
 
    for ( int i = 0 ; i <= n / 3 ; i++ ) {
        int temp = 0;
        temp += i;
 
        if ( ( n - i*3 ) % 5 == 0 ) {
            int fiveKiloBagNum = ( n - i * 3 ) / 5;
            temp += fiveKiloBagNum;
            if ( minTotalBags > temp ) minTotalBags = temp;
        }
    }
 
    if ( minTotalBags == MAX ) {
        cout << -1;
        return 0;
    }
 
    cout << minTotalBags;
 
    return 0;
}
 

 

3kg 봉지가 0개인 조합에서부터 3kg 봉지가 n / 3인 조합까지 모두 한번씩 참조하는 코드입니다.

 

단 n - (3kg 봉지 개수) * 3값이 5로 나누어 떨어지지 않으면 정확히 N 킬로그램을 만들 수 없는 경우이므로 그냥 넘어가면 됩

 

니다.

 

minTotalBags 값이 반복문 이후에도 5000이라면 정확히 N 킬로그램을 만들 수 있는 경우가 하나도 없는 경우이므로 -1을

 

출력합니다.