문제

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

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

풀이

1. 동전 배열 생성 후 오름차순으로 정렬.

2. 만들 수 있는 금액(target)을 1로 설정.

3. 화폐 단위를 순차적으로 탐색하면서 target에 현재 탐색하는 화폐 단위를 더해준다. --> 주어진 화폐 단위로 해당 target을 만들 수 있는지 없는지 알아보는 과정이다!

4. 만약 target이 현재 주어진 동전의 금액 보다 작으면, target은 주어진 동전으로는 만들 수 없는 금액이므로 종료시킨다.

코드를 보면 금방 이해가 되나 구현에서 굉장히 어려움을 많이 겪었다.

★복습 요망!!

코드

import java.util.*;
import java.io.*;

public class Main {

    static int N;
    static int[] coin;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        coin = new int[N];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            coin[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(coin);
        int target = 1;
        // 아래의 로직이 신기함...
        for (int i = 0; i < N; i++) {
            if (target < coin[i])
                break;

            target += coin[i];
        }

        System.out.println(target);
    }
}