BOJ 2437 저울

www.acmicpc.net/problem/2437

2437번: 저울

추가 주어진다면 오름차순 정렬을 해주고 

현재까지의 누적합 + 1 이 현재의 추보다 더 크다면 그 누적합 + 1 이 구할 수 없는 최솟값이 된다.

그 이하의 수들은 현재까지의 추들로 모두 조합할 수 있다.

 

#include <iostream>
#include <algorithm>
using namespace std;

int ar[1001];

int main() {
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) cin >> ar[i];
	sort(ar, ar + n);
	int idx = 1;
	for (int i = 0; i < n; i++) {
		if (idx < ar[i]) break;
		idx += ar[i];
	}
	cout << idx << endl;

	return 0;
}

 

이 문제는 접근이 안돼서 다른 사람들의 풀이를 확인해 보고 풀었는데 다들

누적합 + 1 이 현재의 추보다 작으면 그 누적합까지의 경우는 전부 만들 수 있다고 '가정'하고 귀납법으로 증명했는데

사실 잘 이해가 안간다.. 다음에 다시 풀어봐야겠다.