11047 - 동전 0 [그리디]

출처 : 백준_11047_동전0

문제

Greedy를 적용할 수 있는 가장 기초적인 문제이다. 동전들과 내야하는 값이 주어지면, 최소한의 동전을 사용해서 해당 값을 맞춰야 한다.

동전들 중에서 내야하는 값과 같은 동전이 있으면 해당 동전만 사용해서 리턴한다. 만약 딱 맞춰서 낼 수 있는 동전이 없다면, 내야하는 값보다 작은 동전 중에서 그나마 제일 값에 근접한 동전을 고른다. 그 동전들을 값을 초과하지 않는 선에서 여러개 가져간다. 이렇게 가져가다보면 최소한의 동전 수로 내야하는 값을 맞출 수 있게 된다.

풀이