[이코테][기출] 04. 만들 수 없는 금액

<문제 분석>

N개의 동전이 주어질 때 조합으로 만들 수 없는 양의 정수금액 중 최솟값을 구해야 한다.

 

<풀이 (1) - 15분 소요>

1. for (i=1 to 1,000,000)으로 정수를 하나씩 증가시킨다.

2. N개의 동전을 순서대로 빼본다. (미리 오름차순 정렬을 해놓고 큰수부터 빼자.)

3. 빼서 0이되면 만들 수 있는 정수이므로 i를 증가시킨다.

4. 빼서 0보다 크면 나머지를 계속 뺀다.

5. 빼서 음수면 다음 수를 뺀다.

6. 다 빼도 수가 남아 있으면 정답

 

<코드구현(1) - 17분 소요>

import java.util.Scanner;
import java.util.Arrays;

// [이코테](그리디) 04. 만들 수 없는 금액

public class Main {
    static int N;
    static int A[];
    
    public void InputData() {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        A = new int[N];
        for (int i=0; i<N; i++) {
            A[i] = sc.nextInt();
        }
    }

	public void Solve() {
        int num = 0;
        Arrays.sort(A);
        for (int i=1; i<=1000000; i++) {
            num = i;
            for (int j=N-1; j>=0; j--) {
                num = num - A[j];
                if (num == 0) 
                    break; // 만들어지는 수이므로 탐색중지
                else if (num > 0)
                    continue; // 다음 수를 뺀다.
                else if (num < 0) {
                    num += A[j]; // 빼는 수보다 작으므로 더해서 재진행
                }
            }
            if (num > 0) {
                System.out.println(i);
                break;
            }
        }
	}
    
	public static void main (String[] args)
	{
		Main m = new Main();
		m.InputData();
        m.Solve();
	}
}

 

<해설>

내가 짠 코드보다 더 간단하게 구현을 했다.

먼저 오름차순으로 정렬을 하고, target = 1로 초기화 한 동전의 값이 작거나 같으면 target에 더한다.

잘 이해가 안가지만 실제 손으로 써보면 로직이 성립하는 것을 알 수 있다.

 

예) 1 1 2 3 9

답 : 8

target의 초기값은 1이다.

step	target	만들 수 있는 동전조합	현재 coin	target을 만들 수 있는지 여부
1	1	1	[1]	OK (1 == 1 )
2	2	1+1=2	[1, 1]	OK (2 > 1)
3	3	1+2=3 1+1+2=4	[1, 1, 2]	OK (3 > 2)
4	5	1+3=4 1+1+3=5 1+2+3=6 1+1+2+3=7	[1, 1, 2, 3]	OK (5 > 3)
5	8	1+9=10	[1, 1, 2, 3, 9]	NG (8 < 9)

 

<정답코드>

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