[JAVA] 백준 2839번: 설탕 배달

 

---

문제

• 총 설탕 N 킬로그램이 제공되고 3킬로그램, 5킬로그램 봉지 단위로 가져가야 할 때, 사용해야 하는 봉지 수의 최솟값을 구하는 문제.

 

아이디어

• 3킬로그램 보다는 최대한 단위수가 큰 5킬로그램으로 많이 가져가는 것이 포인트인 그리디 문제.
• 아래 과정을 반복한다.
  • 5로 N을 나눈다.
  • 나눈 나머지에서 3을 한 번 뺀다.
  • 이 두 과정을 N이 1보다 작거나 같을 때까지 반복한다.
• 이렇게 되면 5킬로그램 단위로 최대한 많이 가져갈 수 있게되면서, 필요한 봉지수의 최솟값을 구할 수 있다.

 

풀이

import java.io.*;
import java.util.*;

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

        int N = Integer.parseInt(br.readLine());

        int answer = 0;
        
        // N이 1보다 작거나 같을 때까지 반복
        while(true) {
            // 최대한 5킬로그램 봉지수로 채우기
            if(N%5==0) {
                answer += N/5;
                N %= 5;
            }
            if(N < 2) {
                break;
            }
            
            // 5로 나누어 떨어지지 않은 나머지에서 3킬로그램 한봉지 추가
            N -= 3;
            answer++;
        }
        if(N != 0) {
            answer = -1;
        }
        System.out.println(answer);
    }
}

 

 

채점 결과

2839번 채점 결과

기타

• 드디어 등장한 그리디 문제... 앞으로 잘 풀 수 있을까..

 

문제 링크

• 2839번: 설탕 배달 (acmicpc.net)