찰떡개발자 코딩

최적해를 구하는 데에 사용되는 근사적인 방법, 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해나가는 방식이다.
하지만 선택들을 계속 수집해서 최종적인 해답을 얻었을 경우 이 해답이 최적의 답이라는 보장은 없다. 

적용이 잘되는 경우

1. Greedy Choice Property (탐욕 선택 조건)

• 앞의 선택이 이후 선택에 영향을 주지 않는 경우. 즉, 각 사건들이 서로 독립적일 때 잘 맞는다. 

2. Optimal Substructure (최적 부분 구조 조건)

• 문제에 대한 최적해가 부분 문제에 대해서도 최적인 경우

이문제는 쉬운 문제다 그리디가 뭐지? 하는 나도 풀었던 문제 정리..

문제 : https://www.acmicpc.net/problem/5585

해결 :

public class greedyAlgorithm {

	public static int price;
    public static int count;
    public static int[] coinArr = {500, 100, 50, 10, 5, 1}; //코인 종류
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        price = 1000 - sc.nextInt(); //잔돈= 1000-지불할 금액
 
        //동전이 큰순서대로 정렬되있기 때문에 큰순서대로 동전을 빼서 지불한다.
        for(int coin:coinArr) {
            getCount(coin);
        }
        
        System.out.println(count);
    }
    
    public static void getCount(int coin) {
        count += (price / coin); //지불할 금액 / 동전금액 = 동전 갯수
        price = price - (coin * (price / coin)); // 가격
    }
}