거스름돈 문제

거스름돈 문제는 전형적인 경쟁 프로그래밍 문제이다. 이 문제는 화폐 시스템에 관한 것이다. 이 시스템에는 n가지 액면의 동전 $c1, $c2, . . . , $cn이 있고, c1 = 1이며 c2, . . . , cn은 모두 정수이다. 각 액면의 동전을 무한히 가지고 있다고 하자. 거스름돈 문제는 목표 금액 x가 주어졌을 때 최소 개수의 동전으로 $x를 거슬러 주는 것이다.

거스름돈 문제는 프로그래밍 대회에 매우 자주 등장했다. 많은 참가자가 이 문제를 푸는 방법을 알고 있다. 그러나 잘못 푸는 참가자도 많다. 예를 들어 많은 참가자가 그리디 알고리즘을 사용하는데, 이는 통하지 않는다. 이 그리디 알고리즘은 x를 넘지 않는 가장 큰 액면의 동전을 반복해서 선택한다. 이 알고리즘은 일부 화폐 시스템에서는 실제로 동작하지만 $1, $3, $4에 목표 x = 6인 경우에는 그렇지 않다. 이런 경우를 이 그리디 알고리즘의 반례라고 부르고, x = 6을 화폐 시스템 $1, $3, $4의 증인이라고 한다.

주어진 화폐 시스템에 대해 최소 증인을 구하는 프로그램을 작성하시오. 증인이 존재하지 않거나 최소 증인이 105보다 크면 프로그램은 −1을 출력해야 한다.

첫째 줄에는 화폐 시스템의 액면 수를 나타내는 정수 n이 주어진다. 둘째 줄에는 화폐 시스템이 $c1, . . . , $cn을 가진다는 것을 나타내는 n개의 정수 c1, . . . , cn이 주어진다.

최소 증인 x가 x ≤ 105이면 x를 출력한다. 그렇지 않으면 −1을 출력한다.

• n ≤ 50
• c1 = 1 < c2 < · · · < cn ≤ 105