Greedy algorithm

1. Problem

- 그리디 알고리즘을 이용하여 거스름돈으로 지급할 동전의 최소한의 개수를 구해보자.

- 그리디 알고리즘은 가장 큰 것부터 또는 가장 작은 것부터 선택하며 최적의 답을 찾아가는 알고리즘으로, 탐욕법이라고도 불린다.

- 그리디 알고리즘은 정렬, 다이나믹 프로그래밍과 함께 사용되는 경우가 대다수이다.

- 그리디 알고리즘이 항상 최적의 답을 도출하지는 않는다.

 

2. Input

1) 거스름돈 액수

 

3. Output

1) 거스름돈을 500원, 100원, 50원, 10원짜리 동전을 이용해서 지급할 때 필요한 동전의 최소 개수

 

4. Example

거스름돈으로 지급해야 하는 금액: 947원
// 500 < 947 < 1000
500원: 1
// 남은 금액: 447원
// 400 < 447 < 500
100원: 4
// 남은 금액: 47원
// 47 < 50
10원: 4
// 남은 금액: 7원
// 5 < 7 < 10
5원: 1
// 남은 금액: 2원
1원 : 2
// 따라서 동전의 최소 개수는 1+4+4+1+2=12개

 

5. Code

int money = 947;
int[] coins = {500, 100, 50, 10, 5, 1};
int count = 0, i = 0;
System.out.printf("초기: money=%3d, count=%2d\n",money,count);
while(money>0 && i<coins.length) {
    count += money/coins[i];
    money %= coins[i];
    System.out.printf("%3d원 동전 계산 후: money=%3d, count=%2d\n",coins[i],money,count);
    i++;
}
System.out.printf("최소 개수: %d개",count);
// 출력 결과
초기: money=947, count= 0
500원 동전 계산 후: money=447, count= 1
100원 동전 계산 후: money= 47, count= 5
 50원 동전 계산 후: money= 47, count= 5
 10원 동전 계산 후: money=  7, count= 9
  5원 동전 계산 후: money=  2, count=10
  1원 동전 계산 후: money=  0, count=12
최소 개수: 12개