만들수없는금액

동빈이는 N개의 동전을 가지고 있다. 이 때 N개의 동전을 이용하여 만들 수 없는 양의 정수 금액 중 최솟값을 구하는 프로그램을 작성해라. 예를 들어 N=5이고, 각 동전이 각각 3, 2, 1, 1, 9원이라고 하면 동빈이가 만들 수 없는 양의 정수 금액 중 최솟값은 8원이다. 문제의 시간제한이 1초이고, 동전의 개수가 1000개 이하이므로 O(N^2)도 되겠구나 라는 생각을 했다. 그리고 동전의 단위도 1,000,000이하의 자연수라서 동전의 단위로 반복문을 돈다면 O(NlogN)도 가능하겠다는 생각을 했다. 처음에는 동전들을 오름차순 정렬해서 1부터 가장 큰 동전의 값까지 반복문을 돌려서 1 ~ 동전의 최댓값까지 동전을 만들 수 있는 경우를 확인해보려고 했다. 하지만 그럴 경우 동전의 단위가 서로 나..