백준(boj) 14225 - 부분수열의 합 (부분수열로 만들 수 있는 수)

문제 링크 - https://www.acmicpc.net/problem/14225

👀문제이해 및 풀이방법

부분수열의 합으로 만들 수 있는 수를 계산하는 문제이다. permutation을 사용하여 수를 하나씩 더해보며 모든 경우의 수를 모두 계산하여 답을 찾아냈다. 결국 메모리와 시간적 낭비가 엄청났다. 좋은 방법이 없을까 고민하다 다른 사람의 코드를 보았는데 이건 알아둬야겠다는 생각이 들어 블로그에 남긴다.
수열의 수들을 사용하여 만들 수 있는 수는 수열을 정렬하여 작은 수부터 하나씩 더해간 수까지는 모두 만들 수 있다. 하지만 다음 수가 이전 합+1을 초과하는 경우! 그러니까 [1,2,3,4,5,17] 이 경우에는 1~5까지 사용하여 1~15까지 만들 수 있지만 17이 16을 초과해 버리므로 16은 만들 수가 없다. 알고나면 당연한 내용이지만 알기 전까지는 쉽게 발견되기 힘든 규칙이라는 생각이 든다.

📝코드

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

bool compare(int& a,int& b){
    return a<b;

};
class subsquence{
private:
    vector<int> val;
    int N;
public:
    subsquence(){
        std::cin >> N;
        val.resize(N);
        set_val();
        
    }
    void set_val(){
        for(int i=0;i<N;i++)
            std::cin >> val[i];
        sort(val.begin(),val.end(),compare);

    }
    void find_sol(){
        int sol=1;
        for(int i=0;i<N;i++){
            if(val[i]>sol)
                break;
            sol+=val[i];
        }
        std::cout << sol << '\n';
    }

};
int main(){
    cin.tie(NULL);cout.tie(NULL);
    ios_base::sync_with_stdio(false);
    subsquence ss;
    ss.find_sol();

    return 0;
}