4.만들 수 없는 금액

📍 문제 설명

N개의 동전이 주어질 때 만들 수 없는 양의 정수 금액 중 최솟값을 구하는 프로그램을 작성하시오.

예를 들어, N = 5이고, 각 동전이 3,2,1,1,9원이면 최솟값은 8원

또 다른 예로 N= 3 이고, 각 동전이 3,5,7원이면 최솟값은 1원

입력 조건

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

출력 조건

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

입력 예시

입력

5

3 2 1 1 9

출력

8

💡 접근

만들 수 있는 금액을 확인하기 위한 1원부터 시작하는 target원을 설정해놓는다.

target에 리스트에 담긴 값들을 더해나갈 것임

 

target = 1 (1원을 만들 수 있는지 확인)

-> target = arrayList.get(0) -> 1원 동전 하나로 만들 수 있음

target += arrayList.get(0); (2)

 

target = 2 (2원을 만들 수 있는지 확인)

-> target > arrayList.get(1) -> 1원 동전 두개로 만들 수 있음

target += arrayList.get(1); (3)

 

target = 3 (3원을 만들 수 있는지 확인)

-> target = arrayList.get(2) -> 3원 동전 하나로 만들 수 있음

target += arrayList.get(2); (5)

 

target = 5 (5원을 만들 수 있는지 확인)

-> target > arrayList.get(3) -> 2원 동전 하나 & 3원 동전 하나로 만들 수 있음

-> 4까지의 모든 금액을 만들 수 있다는 말과 같음★★★★

target += arrayList.get(3); (8)

 

target = 8 (8원을 만들 수 있는지 확인)

-> target < arrayList.get(4) -> 8원을 만들 수 없음

-> 해당 동전이 만들 수 없는 최솟값

 

 

👩‍💻 코드

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);
    }
}