알고리즘 :: 백준 :: Bruteforce :: 14225 :: 부분수열의 합

문제

수열 S가 주어졌을 때, 수열 S의 부분 수열의 합으로 나올 수 없는 가장 작은 자연수를 구하는 프로그램을 작성하시오.

문제접근

• https://velog.io/@embeddedjune/알고리즘-백준-DP-1208-부분수열의-합2 보다 쉬운 문제다.
• 과정은 위 링크에서 풀이한 내용의 전반부는 동일하다. front와 back으로 수열의 부분 합 계산 결과를 기록할 필요는 없지만 과정은 동일하다.
• 부분수열의 부분 합 계산 결과를 저장한 뒤, 내림차순으로 정렬한 뒤 가장 앞 요소부터 자연수를 계산한다.
• i번째 요소와 i - 1번째 요소를 비교해서 1 차이가 나지 않으면 그 사이에 자연수가 1개 이상 있다는 의미이므로 해당 자연수를 찾아 return 해준다.

코드

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

int N;
vector<int> vec;

int solve() {
    int partialSize = 1 << N;
    vector<int> partialSum(partialSize);
    for (int i = 0; i < partialSize; ++i)
        for (int j = 0; j < N; ++j)
            if (i & (1 << j)) partialSum[i] += vec[j];
    sort(begin(partialSum), end(partialSum));

    if (partialSum[1] > 1) return 1;
    for (int i = 1; i < partialSum.size(); ++i)
        if (partialSum[i] > partialSum[i - 1] + 1)
            return partialSum[i - 1] + 1;
    return partialSum.back() + 1;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    cin >> N;
    vec = vector<int>(N);    
    for (int i = 0; i < N; ++i) cin >> vec[i];

    cout << solve() << '\n';
}

결과