Part2. 8-8 그리디 알고리즘(여러 종류의 동전으로 가격 지불하는 문제)

그리디(Greedy) 알고리즘

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

문제 정의

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

( 10원이 모여서 50원이 되고 , 50원이 모여서 100원이 될 수 있기 때문에 그리디가 가능하다 --> 가장 단위가 큰 돈 먼저 선택하면 동전의 개수는 무조건 적어진다 )

 

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 + "가 필요합니다.");
		}
	}
}