[Java] 백준 풀기 2839 - 설탕 배달

자바 백준 2839번

실버 4

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

2839번: 설탕 배달

 

 

 

 

 

문제 보기

분류: 수학, 다이나믹 프로그래밍, 그리디 알고리즘

 

 

 

 

 

문제 풀기

설탕 봉지의 개수를 가장 적게 하기 위해서는 5kg 의 개수가 가능한 최대여야 한다. 따라서 주어진 무게에서 5kg 을 나눈 몫을 최대로 두고 5kg 의 봉지를 하나씩 제거하면서 그 남의 무게가 3kg 으로 나누어 떨어지는지 확인한다. 그렇게 나누어떨어지는 시점이 최소 봉지 개수의 반환이며, 남은 무게가 while loop 종료될때까지 나누어 떨어지지 않으면 -1 의 반환이 된다.

 

 

 

 

 

코드 보기

import java.util.Scanner;

public class Main {
    
    public static void main (String args[]) {
        
        Scanner sc = new Scanner(System.in);
        
        int inputWeight = sc.nextInt();
        int result = findMinimumBags(inputWeight);
        
        System.out.println(result);
    }
    
    public static int findMinimumBags (int inputWeight) {
        
        // 주어진 무게를 5kg로 나눈 몫.
        int max5kg = inputWeight / 5;

        // 5kg로 나눈 몫부터 0까지 반복하면서
        // 남은 무게를 3kg로 나눠서 나머지가 0인지 확인.
        while (max5kg >= 0) {
            int remainingWeight = inputWeight - max5kg * 5;
            if (remainingWeight % 3 == 0) {
                // 3kg로 나눠서 나머지가 0이면 최소 개수를 return.
                return max5kg + remainingWeight / 3;
            }
            max5kg -= 1;
        }

        // 주어진 무게를 만들 수 없는 경우 -1을 return.
        return -1;
    }
    
}