[C++] 백준 1182번 - 부분수열의 합

---

0. 문제

 

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

1. 아이디어

 

1) 부분수열의 원소의 개수가 1개부터  N개까지의 케이스들을 나눠서 계산한다.

 

2. 소스코드

 

#include <iostream>
#include <vector>
#include <algorithm>
int main()
{
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0);
    int N, S,result=0;
    std::cin >> N >> S;
    std::vector<int> v; // 수열의 원소가 들어갈 벡터
    for (int i = 0; i < N; i++)
    {
        int input;
        std::cin >> input;
        v.push_back(input);
    }
    for (int i = 1; i <= N; i++)
    {
        std::vector<int> tempV; // 조합을 구할 때 사용할 임시벡터
        for (int j = 0; j < i; j++) // 원소의 개수가 1개부터 N개까지의 부분수열
            tempV.push_back(1); // i개의 '1' 입력
        for (int j = 0; j < N - i; j++)
            tempV.push_back(0); // N-i개의 '0' 입력
        std::sort(tempV.begin(), tempV.end());
        
        do
        {
            int temp = 0;
            for (int j = 0; j < N; j++)
                if (tempV[j] == 1) temp += v[j];
            if (temp == S) result++;
        } while (std::next_permutation(tempV.begin(), tempV.end()));
    }
    std::cout << result;
}

 

3. 결과

 

4. 피드백

 

• 브루트포스를 조금은 감은 잡은듯 하다..
• next_permutation 함수를 이용해서 조합을 구하는 방법을 다시 한번 공부하자.

---

 

TO DO LIST: 순열·조합

---