이것이 취업을 위한 코딩 테스트다 책에 수록된 문제입니다! (교재 314쪽)

문제

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

입력

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

출력

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

예시

5
3 2 1 1 9

위의 입력값에 대한 출력은 8이다.

풀이 과정

나의 접근 방식

target 금액을 1부터 1씩 증가시키면서 해당 금액을 주어진 동전들의 조합으로 만들 수 있는지 검사하려고 했다. 그리고 그 동전들은 당연히 해당 금액 이하의 동전들로 구성된다.

1 1 2 3 9

1
2
3
4 = 3 + 1
5 = 3 + 2
6 = 3 + 2 + 1
7 = 3 + 2 + 1 + 1
8 = 8원 이하의 동전들로 만들 수 없는 금액 → 답: 8

그런데, 이 방법대로 1원씩 증가되는 target 금액을 어떤 동전들의 조합으로 만들 수 있는지 알아내는 로직을 짜기가 어려웠다. 코드를 어떻게 짜야 할지 전혀 감이 오지 않아서 결국 답안을 확인했다.

답안

예를 들어 1, 2, 3원이 주어질 때 우리는 1부터 6원까지의 모든 금액을 만들 수 있다.

1
2
3
4 = 3 + 1
5 = 3 + 2
6 = 3 + 2 + 1

이제 금액 7원도 만들 수 있는지 확인하기 위해서, 새로운 화폐 단위인 5원이 주어졌다고 가정하자. 1, 2, 3, 5원으로는 1부터 11까지의 모든 금액을 만들 수 있다. (당연히 금액 7원도 만들 수 있다.)

1
2
3
4 = 3 + 1
5
6 = 5 + 1
7 = 5 + 2
8 = 5 + 3
9 = 5 + 3 + 1
10 = 5 + 3 + 2
11 = 5 + 3 + 2 + 1

이번에는 금액 12원을 만들 수 있는지 확인하려고 하는데, 새로운 화폐 단위가 13원으로 주어졌다고 가정하자. 1, 2, 3, 5, 13원으로 12원을 만들 수 있을까? 불가능하다. 1, 2, 3, 5원으로 만들 수 있는 최대 금액이 11원인데 남은 화폐 단위가 13원밖에 없으므로 12원은 만들 수 없다.

이러한 규칙에 의하면, 현재 상태를 '1부터 (target - 1)까지의 모든 금액을 만들 수 있는 상태'라고 했을 때, 매번 target인 금액도 만들 수 있는지, 즉 현재 확인하는 동전의 단위가 target 이하인지를 확인해야 한다. 만약 해당 금액을 만들 수 있다면, target의 값을 업데이트 하면 된다.

위의 예시에서는 target이 7원일 때, 현재 확인하는 동전의 단위가 5원이어서 target 금액을 만들 수 있었고, target이 12원일 때는, 현재 확인하는 동전의 단위가 13원이어서 target 금액을 만드는 게 불가능했다.

이 문제를 풀기 위한 알고리즘을 요약하면 다음과 같다.

1. target 금액은 1부터 시작하고 화폐 단위는 오름차순으로 정렬한다.
2. 화폐 단위를 순차적으로 검사하면서 만약 target보다 단위가 작을 경우 해당 target은 만들 수 있다.
3. target을 만들 수 있을 경우, 다음 target은 해당 화폐 단위를 더한 값으로 갱신한다.
4. target보다 큰 값이 검사 단위로 주어질 경우 해당 target은 만들지 못한다고 판단하여 답으로 출력한다.

핵심은 target 이하의 값은 모두 만들 수 있다고 정의하는 것이었다. 화폐 단위가 작은 동전부터 하나씩 확인하면서 target을 증가시키고 가장 작은 target 값을 찾아가기 때문에 그리디 알고리즘으로 분류된다.

이 알고리즘에 맞춰서 문제를 다시 풀어보자. 이번에는 1, 2, 3, 8원이 주어졌다고 가정하자.

target = 1
→ 우리에게는 1원이 있다.
→ target 갱신 = 1 + 1 (1까지의 모든 금액을 만들 수 있다.)

target = 2
→ 우리에게는 2원이 있다.
→ target 갱신 = 2 + 2 (3까지의 모든 금액을 만들 수 있다.)

target = 4
→ 우리에게는 3원이 있다.
→ target 갱신 = 4 + 3 (6까지의 모든 금액을 만들 수 있다.)

target = 7
→ 7원보다 작은 동전들로는 6원까지밖에 못 만들며, 남은 건 7원보다 큰 8원밖에 없다. 그래서 1, 2, 3, 8원으로 만들 수 없는 금액의 최솟값은 7원이다.

C++ 코드

https://github.com/ndb796/python-for-coding-test/blob/master/11/4.cpp

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int main() {
    int n;
    cin >> n;

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

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

    int target = 1;
    for (int i = 0; i < n; i++) {
        // 타겟보다 큰 화폐 단위가 주어지면, 만들 수 없는 금액으로 판단
        if (target < v[i]) 
            break; 

        // 타켓보다 작은 화폐 단위일 경우, 해당 화폐 단위를 더한 값으로 타겟 금액 갱신
        target += v[i];
    }

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

솔직히 답안을 봤는데도 완전하게 이해하지 못해서 다음에 다시 스스로의 힘으로 풀어봐야 한다!!!