[알고리즘] 백준 1940 주몽 // 조합은 재귀로

* next_permutation 풀이

•  단점 : 시간복잡도가 nCr * n 이다. -> 터짐
• 주의점 : arr이 아니고 v를 돌려야함.

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

ll n, m, ret;
vector<int> arr;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n >> m;

    if(m > 200000) {
        cout<<0;
        return 0;
    }

    vector<int> v(n-2,0); // 조합용 벡터
    v.push_back(1);
    v.push_back(1);
    for (int i = 0; i < n; ++i) {
        int tmp;
        cin>>tmp;
        arr.push_back(tmp);
    }
    
    
    do {
        int sum=0;
        for (int i = 0; i < n; ++i) {
            if (v[i]) {
                sum+=arr[i];
            }
        }
        // cout<<sum<<" ";
        if(sum==m) ret++;
    }while(next_permutation(v.begin(), v.end()));
    
    cout<<ret;
}

 

* 재귀조합 풀이

• combi를 -1 로 호출해야함

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

ll n, m, ret;
vector<int> arr;

void combi(int idx, vector<int>& v) {
    if(v.size()==2) {
        int a = arr[v[0]];
        int b = arr[v[1]];
        if(a+b == m) {
            ret++;
        }
        return;
    }
    for(int i=idx+1 ; i<n;++i) {
        v.push_back(i);
        combi(i,v);
        v.pop_back();
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n >> m;

    if(m > 200000) {
        cout<<0;
        return 0;
    }
    
    for (int i = 0; i < n; ++i) {
        int tmp;
        cin>>tmp;
        arr.push_back(tmp);
    }
    
    vector<int> v;
    combi(-1,v);
    
    cout<<ret;
}

 

작동과정