2437 저울

2437. 저울 / c++ / Gold 2 / 1시간

문제

https://www.acmicpc.net/problem/2437

1. 1이상 1,000,000 이하의 무게추가 1 ~ 1’000개 있다.
2. 무게추들의 합으로 구할 수 없는 ‘최소 양의 정수’는 ?

접근 방식

그리디

1. 그리디라는 점에서 일단 ‘최소’ 아니면 ‘최대’를 사용해보려고 했다.
2. 현재 무게추로 나올 수 있는 무게는 [현재 무게추 + 이전 무게추들로 구한 무게들] 이라는 것을 파악.
3. 현재 구해야 하는 무게 [target]을 정하고, 무게추를 오름차순 정렬하여, 낮은 무게부터 더해가면서 target이 나오는지 체크했다.
4. 결국 target을 구한다는 것은 target-1까지의 무게는 모두 나왔다는 뜻이므로, target-1까지 반복해가며 현재 무게추와 더하여 target이 나오는지를 체크했다. (근데 여기서 한번 더 최적화를 해줬어야했다. 아쉽)

문제 풀이

#pragma GCC optimize("Ofast")
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int N;
vector<int> v;

int main()
{
    ios::sync_with_stdio(0); cin.tie(0);

    cin >> N;
    v = vector<int>(N);

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

    sort(v.begin(), v.end());
    int target = 1;
    bool isTarget;
    for (int i = 0; i < v.size(); ++i)
    {
        isTarget = false;
        int size = target;
        for (int j = 0; j < size; ++j)
        {
            if (v[i] + j == target) target++;
            else if (v[i] + j > target)
            {
                isTarget = true;
                break;
            }
        }
        if (isTarget) break;
    }

    cout << target << '\n';

    return 0;
}

다시 생각해 볼 점

1. 제일 가벼운 무게추는 무조건 1이어야한다, 이 조건을 추가해서 처음에 한번 걸러줬어도 좋았을 듯
2. 다른 분의 코드를 보고 파악한 점, 현재까지의 합(sum)보다 다음 무게추의 무게가 2이상 크면 안된다.
3. 이런건 주어진 예시로 파악하려고 하지말고, 한번 ‘어떻게 해야 해당 무게를 못잴까’를 처음부터 낮은 수로 고민해봤으면 좋을 것 같다.