백준 1182번 부분순열의 합

🔒[문제 url]

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

🪄전체 코드

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

int n,s;
vector<int> v;

int ans = 0;

void INPUT()
{
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> s;
    for(int i = 0; i < n; i++)
    {
        int num; cin >> num;
        v.push_back(num);
    }
}

void permutation(int cnt)
{
    /*      IDEA
     * visit의 순열을 돌리며, visit[i] == 1일때 v[i]를 뽑아내면?
     * 원소의 갯수가 cnt인 모든 부분 순열을 뽑아내게 된다!
     * 그 원소들의 합을 구하여 s와 같으면 ans++;
     */

    vector<int> visit;
    // nCk의 조합을 뽑고자 한다면
    for(int i = 0; i < n - cnt; i++) visit.push_back(0); // n - k개의 0
    for(int i = 0; i < cnt; i++) visit.push_back(1); // k개의 1

    do
    {
        int sum = 0;
        for(int i = 0; i < n; i++)
            if(visit[i] == 1)
                sum += v[i];

        if(sum == s) ans++;
    }
    while(next_permutation(visit.begin(), visit.end()));

}

void SOLVE()
{
    // next_permutation을 이용하기 위해선 오름차순 정렬 되어있어야함.
    sort(v.begin(),v.end());
    for(int i = 1; i <= n; i++)
        // 원소가 i개인 부분순열을 구한다.
        permutation(i);

    cout << ans;
}

int main()
{
    INPUT();
    SOLVE();
}

🥇문제 후기

GOLD5 미만 난이도는 알고리즘 및 풀이 설명을 주석으로 대체합니다.
주석을 참고해주세요.