[백준/Baekjoon] 2437 저울 C++ :: Greedy

728x90

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

2437번: 저울

---

1. Logic

- 받은 숫자를 오름차순으로 정렬한다.

 

처음 숫자부터 더해가며

sum > vec[i] 일 경우 수를 조합하여 구할 수 있고

sum < vec[i] 일 경우 현재까지 나온 합 까지 구할 수 있기 때문에 현재 sum 에 + 1을 한 수가 최솟값 이다.

 

 

---

2. Code

#include<bits/stdc++.h>

using namespace std;


vector<int> v;

int main() {
    int n;
    cin >> n;

    for(int i = 0; i < n; i++) {
        int m;
        cin >> m;
        v.push_back(m);
    }

    sort(v.begin(), v.end());

    int res = 1;

    for(int i = 0; i < n; i++){
        if(v[i] > res) break;

        res += v[i];
    }

    cout << res;
}

 

 

---

3. Feedback

- 문제 구현은 엄청 쉬웠지만 누적 합을 통해 로직을 생각해 내는데까지 시간이 엄청 오래 걸렸다. 엄청나게 큰 수까지 가도 과연 이 로직이 참일지 의문이다.