[그리디 알고리즘] 만들 수 없는 금액 ★☆☆

문제 : N개의 동전을 가지고 있을 때 만들 수 없는 금액의 최솟값을 구하라

 

입력 조건

• 첫째 줄에 동전의 개수를 나타내는 양의 정수 N이 주어진다 (1<=N<=1,000)
• 둘째 줄에 동전의 화폐 단위 N개가 주어진다 화폐 단위는 1,000,000 이하의 자연수다

출력 조건

• 첫째 줄에 만들 수 없는 금액 중 최솟값을 출력한다

입력 예시

5
3 2 1 1 9

출력 예시

8

---

고민을 해보았지만 그리디 알고리즘으로 해결하는 방법이 떠오르지 않아 브루트 포스 방법으로 풀어 보았다

 

다음은 그 소스 코드이다

---

#include<bits/stdc++.h>
using namespace std;
int n;
int coin[1001];
bool check[1001];
int ans=1;
int sum;
void chk();
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for (int i = 1;i <= n;i++) cin >> coin[i];
    sort(coin, coin + n);
    chk();
    while (check[ans]) ans++;
    cout << ans;
    return 0;
}
void chk() {
    for (int i = 1;i < (1<<(n+1))-1;i++) {
        sum = 0;
        int val = i;
        for (int j = n;j != 0;j--) {
            int remainder = val % 2;
            val /= 2;
            if (remainder) sum += coin[j];
        }
        check[sum] = true;
    }
}

---

사실 브루트 포스 방법으로 문제를 풀면 대부분의 문제에서 제시하는 시간 내에 해결하지 못할 것을 알고 있었다

 

하지만 바로 답을 보기엔 자존심이 허락하지 않아 일단 문제를 풀고 답을 확인해 보았다

 

그리디 알고리즘의 아이디어는 현재 상황에서 고를 수 있는 가장 좋은 경우를 선택하는 것이다

 

1~(target-1) 금액을 만들 수 있는 경우를 현재 상황이라고 할 때 target을 만들 수 있는가를 체크한다

---

#include<bits/stdc++.h>
using namespace std;
int n;
int coin[1001];
int target=1;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for (int i = 0;i < n;i++) cin >> coin[i];
    sort(coin, coin + n);
    for (int i = 0;i < n;i++) {
        if (target >= coin[i]) target += coin[i];
        else break;
    }
    cout << target;
    return 0;
}