[정올 2499] 저울

http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1760&sca=99&sfl=wr_hit&stx=2499 

JUNGOL

#include <stdio.h>

int N, Cnt, arr[1010], arr2[1010], sum;

void mergesort(int s, int e) {
	if (s >= e) return;
	int m = (s + e) / 2;
	mergesort(s, m);
	mergesort(m + 1, e);
	int k = s, a = s, b = m + 1;
	while (a <= m && b <= e) {
		if (arr[a] < arr[b]) arr2[k++] = arr[a++];
		else arr2[k++] = arr[b++];
	}
	while (a <= m) arr2[k++] = arr[a++];
	while (b <= e) arr2[k++] = arr[b++];
	for (int i = s; i <= e; i++) arr[i] = arr2[i];
}

//정렬 후에 1번부터 시작하며, 각 
int main(void) {
	scanf("%d", &N);
	for (int i = 0; i < N; i++) scanf("%d", arr + i); //입력
	mergesort(0, N - 1); //정렬
	if (arr[0] != 1) printf("1\n"); //제일작은게 1이 아니면 1이 답
	else {
		sum = arr[0];
		for (int i = 1; i < N; i++) { //작은 값부터 돌면서
			if (sum + 1 >= arr[i]) sum += arr[i]; //다음 숫자와 갭이 있다면, 최소값은 1을 더한 것일 것임, 
			//다 더한 값보다 다음 숫자가 더 크다는 것은, 그 갭에서 가장 작은 숫자인 sum + 1이 최소값이라는 것
			//차례대로 갔을 때 이 조건이 보장되지 않는데, 뒤에서 답이 나올 경우는 없다.
			else break; //현재의 s
		}
		printf("%d\n", sum + 1);
	}
	return 0;
}