백준 14225번 : 부분수열의 합 (C++)

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

14225번: 부분수열의 합

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int main() {
    int n;
    cin>>n;
    int arr[n];
    for(int i=0;i<n;i++)
    {
        cin>>arr[i];
    }
    vector<int> v;
    for(int i=1;i<(1<<n);i++)
    {
        int sum=0;
        for(int j=0;j<n;j++)
        {
            if(i&(1<<j))
            {
               sum+=arr[j];  
            }
        }
        v.push_back(sum);
    }
    sort(v.begin(),v.end());
    if(v[0]>1)
    {
        cout<<1;
        return 0;
    }
    for(int i=0;i<v.size();i++)
    {
        if(v[i]==v[i+1])continue;
        if(v[i]+1!=v[i+1] || i==v.size()-1)
        {
            cout<<v[i]+1;
            return 0;
        }
    }
    return 0;
}

 

풀이

15~26행을 통해 가능한 부분 수열의 합을 벡터 v에 넣어준다. 15행의 바깥쪽 반복문에서 1부터 n 자리의 수로 표현 가능한 2진수의 가장 큰 수 까지 돌아가는 반복문을 사용하고 18행의 안쪽 반복문에서 바깥쪽 반복문의 i의 각 자리에 1이라면 배열의 해당 위치의 수를 합쳐준 뒤 모든 자리의 1인 위치의 수를 합친 값을 벡터 v에 넣는 식으로 동작한다.

 그 후에 벡터 v를 정렬하고 v의 가장 작은 수가 1보다 크다면 부분 수열의 합이 1이 없는 것이므로 1을 출력하고 종료한다. 만약 가장 작은 부분 수열의 합이 1이라면 벡터 v를 순서대로 검사하여 다음 인덱스의 수와 다르면서 1 이상 차이가 나거나 마지막 위치인 경우의 다음 값을 출력한 후에 종료해준다.