문제

N개의 동전을 이용하여 만들 수 없는 양의 정수 금액 중 최솟값을 구하는 프로그램을 작성하시오. 1 <= N <= 1000 이며, 각 동전은 1000000이하의 자연수만큼의 가치를 가지고 있다.

입력 조건

• 첫째 줄에는 동전의 개수를 나타내는 양의 정수 N이 주어진다. ( 1 ≤ N ≤ 1000)
• 둘째 줄에는 각 동전의 화폐 단위를 나타내는 N개의 자연수가 주어지며, 각 자연수는 공백으로 구분한다. 이때, 각 화폐 단위는 1,000,000 이하의 자연수

출력 조건

• 첫째 줄에 주어진 동전들로 만들 수 없는 양의 정수 금액 중 최소값을 출력

내 풀이(못함)

23분 정도 사용해서 아무리 고민을 해봐도, 정렬을 한다 라는 아이디어까지만 갔고, 그 이상으로 어떻게 접근해야 할지 몰라서 못했다.

모범 풀이

풀이 과정

단순한 상황을 가정해보자. [1,2,3] 의 가치를 가진 동전만 가지고 있다라고 하면, 1부터 6까지의 모든 경우의 수를 만들 수 있다.

• 1 : 1 한개
• 2 : 2 한개
• 3 : 1 + 2
• 4: 1 + 3
• 5 : 2 + 3
• 6 : 1 + 2 + 3

여기에서 5의 가치를 가진 동전이 들어온다면, 지금까지의 모든 경우의 수에 5를 더해서, 6 ~ 11의 가치를 만드는 방법을 적어도 한가지는 더 만들게 된다. 따라서, 1부터 target 만큼의 조합을 만들 수 있을 때, m의 가치를 가진 동전이 새로 들어오면 1부터 target+m의 모든 조합을 만들 수 있다…

왜 그리디인가?