그리디(Greedy) 알고리즘

1. 지금 상황에서 가장 좋은 해결책을 찾는 알고리즘.

2. 여러 조합에 따른 그 해를 찾는 경우가 많음. 대부분의 조건은 "가장 금액이 큰 순서부터" or "가장면적이 큰 타일을 우선적으로" 등.. 

3. 조건이 명확할 때 정확한 답을 찾을 수 있다.

 

4. 문제 정의

 가게에 놀러간 A는 8370원 어치 물건을 구매했다. 

 A는 동전을 아래와 같이 가지고 있다.

  500원 : 20개

  100원 : 20개

   50원 : 20개

   10원 : 20개의 동전이 있다.

 A는 금액을 지불할 때 단위가 큰 동전부터 지불하려고 한다. A가 지불하게 되는 각 동전의 개수를 구해라.

 

5. code

package GreedyAlgorithm;

public class greedyAlgorithm {

    public static void main(String[] args) {
        int price = 8370;
        int[] coins = {500, 100, 50, 10};
        int[] counts = {20, 20, 20, 20};
        int count;

        for(int i=0; i< 4; i++) {
            count = 0;
            count = price / coins[i];
            price = price % coins[i];
            counts[i] -= count;

            System.out.println(coins[i] + "원짜리 : " + count + "개 필요");

        }
    }
}

*gitHub : https://github.com/bsh6463/algorithm/blob/master/greedyAlgorithm.java

 

6. 결과

500원짜리 : 16개 필요
100원짜리 : 3개 필요
50원짜리 : 1개 필요
10원짜리 : 2개 필요