14225번: 부분수열의 합 (백준 온라인 저지, C++)

문제 해설

 

가능한 부분 수열의 합을 모두 벡터에 넣어주고 벡터를 정렬한 후 unique함수를 활용하여 중복을 배열의 가장 뒤로 보내주었습니다. 이후 인덱스를 비교하여 가장 작은 자연수를 출력시켜 주었습니다.

 

 

코드

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
 
    int n;
    int d[20];
    cin >> n;
    vector <int> v;
 
    for (int i = 0; i < n; i++) {
        cin >> d[i];
    }
 
    v.push_back(0);
    v.push_back(d[0]);
 
    for (int i = 1; i < n; i++) {
        int x = v.size();
        for (int j = 0; j < x; j++) {
            v.push_back(v[j] + d[i]);
        }
    }
 
    sort(v.begin(), v.end());
    unique(v.begin(), v.end());
 
 
    for(int i = 1; i <= v.size(); i++){
        if (i == v.size()) {
            cout << i << '\n';
        }
        else if(v[i] != i){
            cout << i << '\n';
            break;
        }
    }
    return 0;
}

 

 

제출 결과

 

 

 

문제 출처

 

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

14225번: 부분수열의 합