BOJ 2437 저울

문제

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

주어진 무게의 추들 중에 몇개를 골라 만들 수 없는 최소의 무게를 구하는 문제이다.

 

풀이

언뜻 봐서는 dp 문제인듯 하지만, 실제로는 그리디 문제이다.

주어진 추들로 측정할 수 없는 최소 무게를 구하는 것이기 때문에 parametric search 로는 안된다.

 

핵심은 이를 파악하는 것이다.

정렬된 추의 무게 a1, a2, a3, ... 이 있을 때

S = a1+a2+...+ai-1 까지의 무게는 모두 만들 수 있다고 가정하자.

만약 S+1 보다 ai이 더 크다면 S+1은 어떤 방법으로도 만들 수 없다.

크지 않다면 S+ai까지 모든 무게를 만들 수 있다.

이를 귀납적으로 풀면 된다.

 

시간 복잡도 : $O(NlogN)$

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e3;

int n, arr[MAXN+10];

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

    scanf("%d", &n);
    for(i=0; i<n; i++) scanf("%d", &arr[i]);
    sort(arr, arr+n);

    int sum = 0;
    for(i=0; i<n; i++)
    {
        if(sum+1 < arr[i])
        {
            printf("%d", sum+1);
            return 0;
        }
        sum += arr[i];
    }
    printf("%d", sum+1);

    return 0;
}