[BaekJoon][2437] 저울

BAEKJOON ONLINE JUDGE

한국정보올림피아드 2011

2437 저울

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

[참고] 그리디 저울 알고리즘_naver blog

저울의 값을 오름차순으로 정렬하고 하나씩 늘려가면서 무게를 잰다.

원리 : n개의 저울을 다 사용한 무게 < 새로운 저울 이면 그 사이에 존재하는 무게는 잴 수 없다.

n개의 저울을 사용하여 잴 수 있는 무게는 그 이전 무게 또한 부분 개수의 저울을 이용하여 잴 수 있다.

#include <stdio.h>
 
int n;
int num[1001];
 
void quicksort(int start, int end)
{
    int left = start, right = end;
    int middle = num[(start + end) / 2];
    int temp;
 
    while (left <= right) {
        while (num[left] < middle)    left++;
        while (num[right] > middle)    right--;
 
        if(left <= right)    {
            temp = num[left];
            num[left] = num[right];
            num[right] = temp;
 
            left++;
            right--;
        }
    }
 
    if (left < end)       quicksort(left, end);
    if (right > start)    quicksort(start, right);
}
 
int main()
{
    int i, sum = 1;
 
    scanf("%d", &n);
 
    for (i = 0; i < n; i++) {
        scanf("%d", &num[i]);
    }
 
    quicksort(0, n - 1);
 
    if (num[0] != 1)        printf("1\n");
    else {
        for (i = 1; i < n && sum + 1 >= num[i]; i++) {
            sum += num[i];
        }
        printf("%d\n", sum + 1);
    }
 
    return 0;
}