백준14225 - 부분수열의 합

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

14225번: 부분수열의 합

전에 풀었던 2437번과 완전 풀이가 같은 문제다. 그리디를 이용하여 풀었다. 입력 받은 수를 우선 오름차순으로 정렬을 한다. 그 다음 현재까지 더한 숫자보다 1 더 큰 수가 현재 인덱스 숫자보다 작으면 그것이 답이다.

 

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

int main() {
	int n, num, sum = 0;
	vector<int> v;
	
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> num;
		v.push_back(num);
	}

	sort(v.begin(), v.end());

	for (int i = 0; i < n; i++) {
		if (sum + 1 < v[i]) { //현재까지 더한 값보다 1만큼 큰 수가 다음 원소보다 작으면 
			break; //못 만드니까 탈출
		}
		sum = sum + v[i];
	}

	cout << sum + 1; //답으로 현재까지 누적한 값 + 1을 출력
}