#1182 부분수열의 합

문제 정리

N개 정수로 이루어진 수열.
부분수열 원소 합이 S가 되는 경우의 수 출력

생각해보기

피할 수 없는 permutation… 이것도 bruteforce인 것 같은데
부분수열을 어떻게 구하지? 원소 개수 기준으로 하나하나 돌려야하나?
근데 수열이니까 순서는 상관ㄴㄴ. 걍 조합으로 구하면 됨 -> next_permutaion

코드 쓰기

next_permutaion으로 조합을 구하려면 (nCk)
n개의 벡터 원소에 1을 k개, 0을 n-k개 넣어서 순열을 돌리고 1에 해당하는 인덱스만 가져오면 된다!!

그리고… next_permutation은 보통 do-while 문이랑 쓰는 듯?.?

내 풀이

// BOJ-1182 부분수열의 합
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
// 전역 변수
int answer = 0;
int n = 0, s = 0;

// 부분수열 함수
vector<int> getCombination(int elementNum) {
    // 조합 벡터 만들기
    vector<int> comb;
    // 우선 combinaction 원소 개수 N개로 (0) 맞추기
    for(int i=0; i<n; i++){
        comb.push_back(0);
    }
    // elementNum 개수만큼 앞에서부터 1로 바꾸기
    for(int i=0; i < elementNum; i++){
        comb[i] = 1; //이렇게 해도 되나? 안되면 먼저 1 채우고 나머지 개수만큼 0 채우기 -> 된다
      // 마지막에 sort만 해주면 어떤 방식으로 해도 상관 ㄴㄴ
    }

    sort(comb.begin(), comb.end()); // 꼭 넣어야 함 ㅡㅡ

    return comb;
}

int main() {
    // 입력
    cin >> n >> s;

    vector<int> v;
    for(int i = 0; i < n; i++){
        int t = 0;
        cin >> t;
        v.push_back(t);
    }

    // 원소 수 기반 combination vector 얻기
    for(int i = 1; i <= n; i++){
        vector<int> combination = getCombination(i);

        do {

            int sum = 0;
            for(int j = 0; j < combination.size(); j++){
                if(combination[j] == 1){
                    sum += v[j];
                }
            }

            // 정답일 때
            if(sum == s){
                answer++;
            }
        } while (next_permutation(combination.begin(), combination.end()));
        
    }

    cout << answer;


    return 0;
}

풀고 나서 알게된 것

ㄱ- 조합 구할때 1이랑 0 넣고 꼭!!! sort를 해 줘야 한다.
이거 때문에 20분 삽질했다… next_permutation 은 ascending order로 하기 때문에
1먼저 넣고 0을 뒤에 채워버리면 끝났다고 판단해서 (ㅋㅋ) ..

{ 0, 0, 0, 0, 1} 다음 수열은 { 0, 0, 0, 1, 0} 이런식이라서 ㅋㅋㅋㅋㅋㅋㅋ아오