그리디 알고리즘

탐욕 알고리즘이라고도 불리는 그리디 알고리즘은
지금 당장 처해진 상황에서 최적의 답을 선택하는 알고리즘 설계기법입니다.

하지만, 단순히 가장 좋아보이는 것을 선택했지만, 그게 나중에 최적의 해가 되지는 않을 수 있습니다.

그리디 알고리즘을 적용하려면 두가지 조건이 있습니다.

1. 최적 부분 구조

문제에 대한 최적의 해가 부분 문제에 대해서도 최적의 해여야합니다.

2. 탐욕스러운 선택조건

앞의 선택이 이후 선택에 영향을 주지 않아야 합니다.

만약, N이 1260원일 때, 다양하게 거슬러줄 수 있지만
최소개수로 거슬러주는 방법은 500원부터 거스름돈을 채워나가는 방법일 것이다.
그래서 500원으로 거슬러주고 남는 돈을 100원 그리고 50원 10원 순으로 하면 최적의 방법이 될 수 있다.

public static void main(String args[]) {
		int sum = 1260;
		int a[] = {500,100,50,10};
		int count = 0;

		for(int i=0; i < a.length ; i++){
			count += sum / a[i];
			sum = sum % a[i];
		}
		System.out.print(count);
	}