[그리디] 만들 수 없는 금액

문제

당신은 N개의 동전을 가지고 있습니다. 이때 N개의 동전을 이용하여 만들 수 없는 양의 정수 금액 중 최솟값을 구하는 프로그램을 작성하세요.

예를 들어, N = 5이고, 각 동전이 각각 3원, 2원, 1원, 1원, 9원짜리 동전일 때, 만들 수 없는 양의 정수 금액 중 최솟값은 8원입니다.

 

입력 조건

• 첫째 줄에는 동전 개수를 나타내는 양의 정수 N (1 <= N <= 1,000)
• 둘째 줄에는 각 동전의 화폐 단위를 나타내는 N개의 자연수 (1,000,000 이하의 자연수)

출력 조건

• 만들 수 없는 양의 정수 금액 중 최솟값 출력

입력 예시

5
3 2 1 1 9

 

출력 예시

8

---

아이디어

• 우선, 오름차순으로 정렬한다. 이후에 1부터 차례대로 특정한 금액을 만들 수 있는지 확인하면 된다.
• 1부터 차례대로 단계를 거쳐 특정한 금액(target)을 만들 수 있는지 검사
• 1부터 특정한 target-1까지의 모든 금액을 만들 수 있다고 가정해보자
• 화폐 단위가 작은 순서대로 동전을 확인하며, 현재 확인하는 동전을 이용해 target금액 또한 만들 수 있는지 확인한다. 
• 여기서 현재 확인하는 동전금액이 target보다 이하여야 그 동전을 이용하여 target을 만들 수 있다.
• 만약 해당 target 금액을 만들 수 있다면 target의 값을 업데이트한다.

---

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
arr = new int[N];
String[] input = br.readLine().split(" ");
for(int i = 0; i < N; i++){
    arr[i] = Integer.parseInt(input[i]);
}

Arrays.sort(arr);

int target = 1;
for(int i : arr) {
    if(target < i)
        break;
    target += i;
}
System.out.println(target);