[Problem Solving] BOJ 2437 : 저울

문제 링크 : https://www.acmicpc.net/problem/2437

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <map>
#include <algorithm>
#include <set>
#define endl '\n'
using namespace std;

int N, S = 0;
vector<int> v;

void input()
{
    cin >> N;
    v.resize(N);
    for (int i = 0; i < N; i++)
    {
        cin >> v[i];
    }
}

void solution()
{
    sort(v.begin(), v.end());

    for (int i = 0; i < v.size(); i++)
    {
        if (v[i] <= S + 1)
            S += v[i];
        else
            break;
    }
}

void output()
{
    cout << S + 1 << endl;
}

int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    input();
    solution();
    output();

    return 0;
}

  

v : {3, 1, 6, 2, 7, 30 ,1}이라고 하자.

이를 정렬하면 {1, 1, 2, 3, 6, 7, 30} 이다.

현재까지 만들 수 있는 수는 S : 0이라고 하자.

 

1. 1을 만들 수 있는가? -> num[0] = 1 <= 1 이기 때문에 1을 만들 수 있다.

2. 2를 만들 수 있는가? -> num[1] = 1 <= 2 이기 때문에 2을 만들 수 있다.

3. 3을 만들 수 있는가? -> num[2] = 2 <= 3이기 때문에 3부터 4까지 만들 수 있다.

4. 5를 만들 수 있는가? -> num[3] = 3 <= 5이기 때문에 5부터 7까지 만들 수 있다.

5. 8을 만들 수 있는가? -> num[4] = 6 <= 8이기 때문에 8부터 13까지 만들 수 있다.

6. 14를 만들 수 있는가? -> num[5] = 7 <= 14이기 때문에 14부터 20까지 만들 수 있다.

7. 21을 만들 수 있는가? -> num[6] = 30 <= 21이기 때문에 21은 만들 수 없다.

8. 21 출력.