[Algorithm][오답노트] [이코테] 4. 만들 수 없는 금액

문제

편의점 주인인 동빈이는 N개의 동전을 가지고 있다.
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

느낀점

이 문제는 처음 보면 그리디 알고리즘이라고 생각하기 힘든 문제였다.

하지만 알고나면 너무 쉬운 문제다.

하나의 유형이라고 생각하고 외워두면 좋을 것 같다.

 

문제를 풀어내는 사고방식은 다음과 같다.

작은 동전부터 탐색하면서, 만들고자 하는 금액(target)을 아직 이용하지 않고 가장 작은 금액의 동전이 만들고자 하는 금액 이하이면 해당 금액을 그 전에 이용한 동전과 조합해 만들 수 있다.

그 전에 이용했던 동전들로 1~target-1의 금액을 만들 수 있고 이용하지 않은 가장 작은 금액의 동전이 target 보다 작다면
     이용하지 않은 가장 작은 금액의 동전 ( <= target) + (1~target-1) ∋ target

이 성립한다.

따라서 동전들을 정렬한 후, 하나씩 뽑으면서 다음 target을 업데이트해주면 된다.

 

#include <iostream>
#include <vector>

using namespace std;

int n;

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

    // 1. 정렬
    sort(v.begin(), v.end());

    // 2. 첫번째 target은 1, 이용하기 전의 가장 작은 동전이 target이하여야 target을 만들 수 있다.
    int target = 1;
    for (int i = 0; i < n; i++) {
        if (v[i] <= target) {
            target += v[i];
        }
        else {
            // 만들 수 없는 금액 종료
            break;
        }
    }

    cout << target << "\n";

    return 0 ;
}