탐욕알고리즘 - 1

// 코인문제 p.57
/**
  1, 5, 10, 50, 100, 500원짜리가 각각 C1, C5, C10, C50, C100, C500개씩 있다.
  A원을 지불하려면 몇 개의 동전이 있어야 할까. 지불 방법은 적어도 1개는 존재한다고 가정한다.
  **/
import java.io.*;

class Main {
  public static void main(String[] args) throws IOException {
    int ans = 0;
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    // BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    final int[] V = {1,5,10,50,100,500};
    int[] C = {3,2,1,3,0,2};
    int A = 620;

    // 큰 것부터 넣는다. 탐욕알고리즘
    for (int i = 5; i >= 0; i--) {
      int t = min(A / V[i], C[i]); // 
      A -= t * V[i];
      ans += t;
    }
   
    bw.write("ans : " +  ans + "\n"); // 출력 6(500x1, 50x2, 5x2 합계 6개)
    bw.close();
    // br.close();
  }
  public static int min(int a, int b) {
    if (a > b) return b;
    else return a;
  }
}