[Algorithm] Greedy 설탕 배달 (백준) - 에이젠

 

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

2839번: 설탕 배달

공략

백준 알고리즘 분류에서 그리디 알고리즘 첫번째 문제 입니다.

그리디는 최적에 해에 가까운 값을 찾을 때 사용되며

매 순간 최적이라고 생각되는 경우를 선택하며 반복합니다.

 

문제에서 이와 같은 방식으로 풀어보겠습니다.

5kg 봉지와 3kg봉지에 Nkg의 설탕을 담아 배달한다고 합니다.

어떻게 담아야 봉지 개수를 최소로 할 수 있을까요?

직관적으로 5kg이 많을수록 봉지 개수가 최소한인 최적의 값인 것을 알 수 있죠.

따라서 먼저 Nkg을 담을 수 있는 5kg 봉지 최대 개수를 구합니다. 

그리고 남는 설탕을 3으로 나누어 3kg의 봉지 개수를 구합니다.

만약 나누어 떨어지지 않는다면 5kg 봉지를 하나씩 줄이고 위 과정을 반복합니다.

 

import java.util.*;

public class Main {

  static Scanner sc = new Scanner(System.in);
  // 설탕 Kg
  static int N;

  static void input() {
    N = sc.nextInt();
  }

  // 18 -> 4
  // 4 -> -1
  // 6 -> 2
  // 9 -> 3
  // 11 -> 3
  static void findAnswer() {
    // 최소 봉지 개수 찾기

    // 5 * a + 3 * b = N
    int a = N / 5;
    int b = (N - a * 5) / 3;

    while (5 * a + 3 * b != N) {
      a--;
      b = (N - a * 5) / 3;
      if (a < 0) {
        a = -1;
        b = 0;
        break;
      }
    }

    System.out.println(a + b);

  }

  public static void main(String[] args) {
    input();
    findAnswer();
  }

}