백준 2437 저울 (C++)

2437번: 저울

그리디 방식으로 푸는 문제이다. 풀이 방식 자체는 간단하다. 예를 들어 1, 2, 4, 15 배열을 왼쪽부터 접근한다고 가정해보자. 첫 무게인 1의 경우 1 ~ 1만 측정이 가능하다. 2의 경우 이전의 범위에 더한 1 + 2 ~ 1 + 2, 즉 1 ~ 3까지 가능하다. 4의 경우 1 ~ 7까지 가능하다. 15 차례일 때 최대 범위의 다음 값인 8보다 크므로 7까지 측정이 가능하다. 이 아이디어를 기반으로 문제를 풀었다.
생각보다 어려웠던 문제였다. 단순히 완전 탐색을 이용하면 분명 시간 초과가 날 것 같았고, 이전 값들을 이용하는 어떤 방식이 있을 것이라고 생각했다. 차례대로 값을 구해보면서 아이디어를 떠올릴 수 있었다. 그리디 유형 문제들을 더 풀어봐야 겠다.

#include <iostream>
#include <algorithm>

using namespace std;

int N;
int A[1000];

void solution() {
    sort(A, A + N);

    int sum = 0;
    for (int i = 0; i < N; i++) {
        if (sum + 1 < A[i]) break;
        sum += A[i];
    }

    cout << sum;
}

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

    cin >> N;

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

    solution();

    return 0;
}