[그리디] 만들 수 없는 금액
N 개의 동전을 가지고 있고, 화폐 단위는 1,000,000 이하의 자연수다. 이때 N 개의 동전을 이용하여 만들 수 없는 양의 정수 금액 중 최솟값을 구해라. 예를 들어 N = 5이고 각 동전이 3원, 2원, 1원, 1원, 9원 이라면 만들 수 없는 양의 정수 금액 중 최솟값은 8원이다. 또 다른 예로 N = 3이고 각 동전이 3원, 5원, 7원 이라면 답은 1원이다. 문제를 보고 처음든 생각은 이랬다. 가능한 모든 수를 Set으로 저장해놓고 1부터 1,000,000 까지 for문 돌려서 없는 숫자가 나오면 답인것으로. 그런데 모든 수를 구하기 위한 방식이 마땅치 않았다. 답 코드를 보면 먼저 정렬 한 후에, 구해야 되는 target 숫자를 차례차례 체크하는 방식으로 이루어져 있다. 예를 들어 data..
2021. 10. 3.
