[Algorithm] Greedy 동전0 (백준) - 에이젠

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

11047번: 동전 0

 

공략

백준 알고리즘 분류가 아닌 온라인 강의에 있는 문제를 따라가면서 풀기로 계획을 바꾸었습니다.

알고리즘 중급 1/3 의 그리디 첫번째 문제입니다.

그리디 알고리즘을 처음 소개한대로 이번 문제도 매 순간 최적의 값을 찾아 반복하면 되겠습니다.

목표한 K원만큼을 최소한의 동전으로 채우는 것이 목표입니다.

가치가 큰 동전을 최대한 많이 사용하는 것이 최적의 동전 개수를 구할 수 있는 거겠죠?



import java.util.*;

public class Main {

  static Scanner sc = new Scanner(System.in);
  // 동전 개수
  static int N;
  static int K; // 목표 금액
  static int[] value; // 동전 별 가치
  static int[] numOfCoin;
  static int total = 0;

  static void input() {

    N = sc.nextInt();
    K = sc.nextInt();
    numOfCoin = new int[N + 1];
    value = new int[N + 1];
    for (int i = 1; i <= N; i++) {
      value[i] = sc.nextInt();
    }

  }
  // 동전 개수의 최솟값을 출력한다.
  // 가장 큰 가치의 동전의 최댓값 -> 최적의 값.

  static void findAns() {
    int k = K;

    for (int i = N; i > 0; i--) {

      numOfCoin[i] = K / value[i];
      K = K - (numOfCoin[i] * value[i]);
      total = total + numOfCoin[i];
      if (K <= 0) {
        // 종료
        System.out.println(total);
        return;
      }

    }
    System.out.println(total);

    // 한번 돌았는데 부족할 때 ? -> 존재 안 함.

  }

  public static void main(String[] args) {

    input();
    findAns();
  }
}