[BOJ 백준] 14225번 부분수열의 합

문제

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

14225번: 부분수열의 합

접근

2중 for문을 이용해 모든 경우의 수에 따른 계산 결과를 구해보았다. 이때 set을 사용해 중복되는 값은 걸러주고, set의 오름차순 정렬을 통해 1부터 체크하여 등장하지 않는 가장 작은 수를 구할 수 있었다.

코드

#include <iostream>
#include <set>
#include <vector>

using namespace std;

int main() {
    int n, num[30];
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> num[i];
    }

    set<int> s;
    for (int i = 0; i < n; i++) {
        vector<int> add;
        for (auto it = s.begin(); it != s.end(); it++) {
            add.push_back(*it + num[i]);
        }
        s.insert(num[i]);
        for (int j = 0; j < add.size(); j++) {
            s.insert(add[j]);
        }
    }
    int counter = 1;
    for (auto it = s.begin(); it != s.end(); it++) {
        if (*it != counter) {
            cout << counter;
            return 0;
        }
        counter++;
    }
    cout << counter;
} 

 

깃 허브 주소 : https://github.com/algoribi/algorithm-study