여러 종류의 동전으로 가격 지불하는 문제(Greedy 알고리즘)

그리디(Greedy) 알고리즘

• 다른 용어로 탐욕 알고리즘이라고도 함
• 지금 상황에서 가장 좋은 해결책을 찾는 알고리즘으로 실제 여러 알고리즘 테스트에서도 흔히 볼 수 있는 문제중 하나임
• 여러 조합에 따른 그 해를 찾는 경우가 많고 이때 제시되는 대부분의 조건은 "가장 금액이 큰 순서부터" 라던가 "가장 면적이 큰 타일을 우선적으로"등의 방식에 제시
• 이 알고리즘은 조건이 명확할 때 정확한 답을 찾을 수 있고, 기존의 다른 알고리즘의 지식이 없어도 상식적인 범위에서 코딩이 가능하다.

문제 정의

• 가게에 간 철수는 8370원 어치 물건을 구매하였습니다. 철수에게는 500원짜리 20개 100원짜리 20개 50원짜리 20개 10원짜리 20개의 동전이 있습니다. 철수는 금액을 지불 할 때 단위가 큰 동전부터 지불하려고 합니다. 철수가 지불하게 되는 각 동전의 개수를 구하세요

문제 해결

• 이러한 문제의 경우 철수는 우선 500원짜리 동전부터 사용할 것이다. 간단하게 계산을 해보면 8370 = 500 * 16 + 100 * 3 + 50 * 1 + 10 * 2 가 된다.
• 가장 큰 동전을 이용하여 지불할 수 있는 최대 금액을 지불하고 그 다음 큰 금액의 동전을 지불하는 순서로 구현한다
• 동전의 종류만큼 반복문이 수행된다.

public class GreedyTest {

	public static void main(String[] args) {

		int[] coins = {500, 100, 50, 10};   // 
		int price = 8370;
		int count;
		
		for (int i = 0; i< coins.length; i++) {
			count = 0;
			count += price / coins[i];
			price = price % coins[i]; 
			
			System.out.println( coins[i] + "짜리 동전 " + count + "가 필요합니다.");
		}
		
	}

}