그리디 탐욕적 알고리즘

그리디 알고리즘

• 그리디 알고리즘은 현재 상황에서 지금 당장 좋은 것만 고르는 방법이다
• 일반적인 그리디 알고리즘은 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구한다
• 그리디 해법은 정당성 분석이 중요하며 단순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적에
  해를 구할 수 있는지 검토가 필요하다

문제 확인

최소 동전 확인 하기

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

  public static void main(String[] args) throws IOException {
    int n = 1260;
    int cnt = 0;
    int[] coinTypes = { 500, 100, 50, 10 };

    for (int i = 0; i < coinTypes.length; i++) {
      cnt += n / coinTypes[i];
      n %= coinTypes[i];
    }
    System.out.println(cnt);
  }
}