백준 2437번 저울[골드 2][C++]

1. 개요

 안녕하세요. 이 문제의 유형은 그리디입니다. 이 문제는 유형을 구분하기에도 조금 힘들었던 문제였습니다. 이유는 발상이 어려운데요. 문제의 데이터 크기 조건을 확인하지 않으면 knapsack 문제로 해석도 가능합니다. 가능한 모든 데이터가 10억이라 DP로 풀이할 시 MLE와 TLE를 피할 수 없습니다. 

 

2. 문제 풀이

 우선 입력으로 들어오는 저울추의 무게를 오름차순으로 정렬합니다. 그 다음 만들 수 있는 숫자의 범위를 결정해야 합니다. 만들 수 있는 최소 무게는 모든 저울추를 제외한 경우인 0입니다. 따라서 처음 가능 범위는 [ 0, 1 )입니다. 이제 정렬된 저울추의 무게 리스트를 순회하면서 무게 1을 만들 수 있는지 비교해야 합니다. 

 

 1이 아닌 임의의 자연수 K에 대해서 [ 0, K )까지 무게를 만들 수 있다고 가정해봅시다. 그리고 비교할 저울추의 무게가 K와 같거나 작은 자연수 X라고 한다면 0 ~ K - 1의 숫자에 X를 더한다면 [ 0 , K + X )까지의 숫자를 만들 수 있습니다.

 

 K를 6, X를 3이라고 가정해봅시다. 0, 1, 2, 3, 4, 5까지의 숫자를 저울추를 이용해 만들 수 있습니다. 다음 저울추의 무게는 3입니다. 0부터 5까지 3을 더하면 3, 4, 5, 6, 7, 8의 숫자를 만들 수 있습니다. 따라서 [ 0, 9 )까지의 범위의 숫자를 만들 수 있습니다. 이때 9 = K + X = 6 + 3이 됩니다.

 

 저희가 구하고자하는 수는 저울추로 만들 수 없는 숫자입니다. 따라서 [ 0, K ) 범위에서 다음 저울추로 K를 만들 수 없다면 K가 정답이 됩니다. 1을 만들 수 없다면 정답은 1이 돼야 하므로 초기 범위는 [ 0, 1 )이 됩니다

 

3. 코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pi; typedef pair<ll, ll> pl;
typedef tuple<int, int, int> ti; typedef tuple<ll, ll, ll> tl; typedef vector<int> vi; typedef vector<ll> vl;
typedef vector<pi> vpi; typedef vector<pl> vpl; typedef vector<ti> vti; typedef vector<tl> vtl;
typedef vector<string> vs; typedef vector<bool> vb; typedef queue<int> qi; typedef queue<ll> ql;
typedef queue<pi> qpi; typedef queue<pl> qpl; typedef queue<ti> qti; typedef queue<tl> qtl;
#define fastio(x, y) cin.tie((x))->sync_with_stdio((y))
#define X first
#define Y second
#define pb push_back
#define sz(x) (int((x).size()))
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
const char nl = '\n';

int n;
vi a;

int main() {
    fastio(nullptr, false);

    cin >> n;
    a.resize(n);
    for(int i = 0; i < n; i++) {
        cin >> a[i];
    }

    sort(all(a));
    
    int ans{1};
    for(int i = 0; i < n; i++) {
        if(ans >= a[i]) {
            ans += a[i];
            continue;
        }   
        break;
    }

    cout << ans;
}

 

4. 제출 결과