BOJ 백준온라인져지 11047 동전 0 풀이

Greedy Algorithm은 그 상황에 따라 그 상황이 최적이라고 가정하고, 최적해를 구하는 방법이다.

결론적으로는 해답에 도달한다.

하지만 그 선택들을 수집해서 최종적인 답이 최적이라는 보장이 없다.

Greedy Algorithm은 대부분 두 가지 조건이 만족된다.

1. 탐욕스런 선택 조건(Greedy Choice Proerty): 앞의 선택이 뒤에 영향을 주지 않는다.
2. 최적 부분 구조 조건(Optimal Substructure): 문제에 대한 최적해가 부분문제에 대해서도 최적해다.

문제로 돌아오면,

 K를 만드는 최소의 Ai 개수를 구하는 것이다.

풀이 방법은

오름차순으로 정렬된 동전의 가치를 저장한다.

내림차순으로 동전과 K의 가치를 비교한다. 동전의 가치가 더 크다면 그 동전은 사용하지 않고,

다음 동전으로 넘어간다.

K 가치가 더 큰게 나오면 K -= (K / Ai) * Ai를 해준다.

몇개를 사용하는지 체크해주기 위해 result += (K / Ai)를 해준다.