[BOJ] 2437 : 저울 - travelbeeee

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

---

[ 알고리즘풀이 ]

1. 가지고 있는 추를 sorting 한 후 무게가 작은 추부터 하나씩 사용해가며 무게를 만들어간다.

2. 내가 현재 1 ~ Weight 까지 무게를 다 만들 수 있었다면 i번 째 추를 추가로 사용하면 n[i] ~ n[i] + Weight 까지의 무게를 추가로 만들 수 있다. 이때, 1 ~ Weight U n[i] ~ n[i] + Weight 의 합집합이 빈 부분이 생긴다면 그 무게는 만들 수 없다. 즉, n[i] 가 Weight + 1 보다 커버리면 만들 수 없는 무게가 생긴다. 

#include<iostream>
#include<algorithm>
#define MAX 1000000
using namespace std;

int N, n[1000] = {};

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);


	cin >> N;
	for (int i = 0; i < N; i++)
		cin >> n[i];

	sort(n, n + N);

	int ans = 0;
	for (int i = 0; i < N; i++) {
		if (n[i] > ans + 1) {
			break;
		}
		ans += n[i];
	}
	cout << ans + 1;
	return 0;
}

---