124. 만들 수 없는 금액

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

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

• 입력조건

  • 첫째 줄에는 동전의 개수를 나타내는 양의 정수 N이 주어집니다. (1 ≤ N ≤ 1,000)

  • 둘째 줄에는 각 동전의 화폐 단위를 나타내는 N개의 자연수가 주어지며, 각 자연수는 공백으로 구분합니다.

    • 이때 각 화폐단위는 1,000,000 이하의 자연수 입니다.

• 출력조건

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

1. 그리디 알고리즘

n = int(input())
data = list(map(int, input().split()))
data.sort()

target = 1
for i in data:
  #만들 수 없는 금액을 찾았을 때 반복 종료
  if target < i:
    break
  target += i

#만들 수 없는 금액 출력
print(target)

• N = 4, 화폐단위는 1, 2, 3, 8이라고 가정해보자.
  
  

  1) 처음에는 금액 1을 만들 수 있는지 확인하기 위해, target = 1로 설정한다.

  2) target = 1을 만족할 수 있는지 확인한다.

  • 우리에게는 화폐가 1인 동전이 있다. 우리는 이 동전을 이용해서 금액 1을 만들 수 있다.

    • 1까지의 모든 금액을 만들 수 있다는 말과 동일

  • target = 1 + 1 = 2로 업데이트

  3) target = 2를 만족할 수 있는지 확인한다.

  • 우리에게는 화폐 2인 동전이 있다. target = 2 + 2 = 4가 된다.

  • 3까지의 모든 금액을 만들 수 있다는 말과 동일

  4) target = 4를 만족할 수 있는지 확인한다. 우리에게는 화폐 단위 3인 동전이 있다. target = 4 + 3 = 7이 된다.

  • 6까지의 모든 금액을 만들 수 있다는 말과 동일

  5) target = 7을 만족할 수 있는지 확인한다. 우리에게는 이보다 큰 확폐단위가 8인 동전이 있다.

  • 따라서 금액 7을 만드는 방법은 없다. 따라서 정답은 7이 된다.

2. C++ 코드

#include <bits/stdc++.h>

using namespace std;

int n;
vector<int> arr;

int main(void) {
    cin >> n;

    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        arr.push_back(x);
    }

    sort(arr.begin(), arr.end());

    int target = 1;
    for (int i = 0; i < n; i++) {
        // 만들 수 없는 금액을 찾았을 때 반복 종료
        if (target < arr[i]) break;
        target += arr[i];
    }

    // 만들 수 없는 금액 출력
    cout << target << '\n';
}

3. Java 코드

import java.util.*;

public class Main {

    public static int n;
    public static ArrayList<Integer> arrayList = new ArrayList<>();

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();

        for (int i = 0; i < n; i++) {
            arrayList.add(sc.nextInt());
        }

        Collections.sort(arrayList);

        int target = 1;
        for (int i = 0; i < n; i++) {
            // 만들 수 없는 금액을 찾았을 때 반복 종료
            if (target < arrayList.get(i)) break;
            target += arrayList.get(i);
        }

        System.out.println(target);
    }
}