[Java] 백준 2839 설탕 배달 - 실버4

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

2839번: 설탕 배달

 

 

문제풀이

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int weight = Integer.parseInt(br.readLine().strip());

		//5kg봉지를 최대한으로 넣은 후, 하나씩 빼면서 성립하는 지 확인
        int cnt5 = weight / 5;
        int cnt3 = 0;
        while (cnt5 >= 0) {
            int tmpWeight = (weight - cnt5*5);
            if (tmpWeight % 3 == 0) {
                cnt3 = tmpWeight / 3;
                break;
            }

            cnt5 --;
        }

       if (cnt5 == -1 && cnt3 == 0)
           System.out.println("-1");
       else
           System.out.println(cnt5 + cnt3);
    }
}

 

• 딱 보면 알 수 있는 그리디 문제다
• 봉지수를 가장 적게하려면 5kg봉지가 최대한으로 들어가야한다
• 일단 5kg봉지를 가장 많이 넣는 경우가 가능한지 확인하고, 5kg봉지를 하나씩 빼면서 정답인지 확인한다.
• 만약 5kg봉지를 하나도 넣지않고 3kg봉지만으로 해결이 되지 않는다면 -1을 출력한다.