[백준] 2437번. 저울 (C++)

문제

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

풀이

[누적합]

문제의 예시 1 1 2 3 6 7 30 를 살펴보자

 

1 → 1 (숫자 1로만 만들 수 있는 숫자)

1 → 1 2 (숫자 1, 1로 만들 수 있는 숫자)

2 → 1 2 3 4 (숫자 1, 1, 2로 만들 수 있는 숫자)

3 → 1 2 3 4 5 6 7

6 → 1 2 3 4 5 6 7 8 9 10 11 12 13

7 → 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

30 → 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 31 32 33 34 35.....50

 

여기서 각각 1 2 4 7 13 20까지는 숫자가 연속된다.

하지만 30은 20 보다 크므로

21이 아니라 31 부터 50까지를 표현할 수 있다.

따라서 20+1이 정답이다.

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
	int sum = 0;
	int N; cin >> N;
	vector<int>number(N);
	for (int i = 0; i < N; i++) { cin >> number[i]; }
	sort(number.begin(), number.end());

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