그리디(greedy) - 만들 수 없는 금액의 최솟값

1. 문제 해결의 아이디어

만들 수 없는 최솟값을 찾으려면 가장 작은 값부터 만들 수 있는지 없는지를 확인하면 된다.
따라서 입력 받은 동전을 작은 단위 순으로 정렬하고 하나씩 꺼내면서 목표 금액(target)을 만들 수 있는지 확인하는 작업을 반복한다.

동전의 단위가 자연수이므로, 확인해야 할 금액은 1부터 시작한다.
따라서 target을 1로 정하고 동전을 꺼내기 시작한다.

만약 꺼낸 동전의 단위가 1보다 크면 1을 만들 수 없으므로 1이 답이된다.
만약 꺼낸 동전의 단위가 1이면 1을 만들 수 있으므로 target을 2로 변경한다.

다음에도 마찬가지로 꺼낸 동전의 단위가 2보다 크면 2를 만들 수 없으므로 2가 답이된다.
만약 꺼낸 동전의 단위가 2 이하, 즉 1 또는 2이면 target을 만들 수 있으므로 target을 변경해야 하는데,
여기서 만약 1이 나왔다면 3을 확인해야 하지만, 2가 나왔다면 앞에 나온 1과 더해져 3이 된다는 것이 바로 확인되므로
다음 target을 3으로 할 필요가 없어진다.
따라서 다음 target은 4가 되는데, 이는 현재 target에 방금 꺼낸 동전의 단위를 더한 금액에 해당한다.

위에서 나온 동전의 단위가 1과 2라고 하자.
그러면 다음 target은 4가 되고, 동전을 하나 더 꺼낸다.
이때 꺼낸 동전의 단위가 4보다 크면 4를 만들 수 없으므로 4가 답이 된다.
만약 4이하라면 4를 만들 수 있으므로 다음 target을 정한다.
방금 꺼낸 동전의 단위가 4라면 현재 확인된 동전은 1, 2, 4이고, 이들을 가지고 7까지 만들 수 있으므로
다음 target은 8이 되며, 이는 역시 현재 target인 4에 방금 꺼낸 동전의 단위인 4를 더한 값임을 알 수 있다.

이러한 방식으로 target을 변경하고 확인하는 작업을 반복한다.

 

2. 소스 코드

위의 아이디어를 코드로 옮기면 다음과 같다.

 

3. 정리

  - 그리디/구현

  - 정렬