BOJ - 카드 놓기 (5568)

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

5568번: 카드 놓기

 

전형적인 조합론 문제입니다.

n개 중에서 k개를 뽑는 함수를 만들고, next_permutaion 함수를 사용해 순열을 구합니다.

이때 중복되는 것은 set 으로 처리해주면 됩니다.

 

#include <bits/stdc++.h>
 
using namespace std;
 
int n, m;
int k;
vector<int> v, vv;
set<string> st;                // 중복처리를 위한 자료구조
 
void sol(int picked, int limit, int cur) {    // picked : 현재 고른 카드의 수, limit : 최대고를 수 있는 카드 수, cur : 현재 고른 카드의 위치
    if (picked == limit) {                    // 모두 골랐으면 이를 처리해주고 return 한다.
        do {
            string s = "";
            for (int i = 0; i < vv.size(); i++) s += to_string(vv[i]);    
            st.insert(s);
        } while (next_permutation(vv.begin(), vv.end()));    // 순열을 통해서 만들 수 있는 숫자를 만들어본다.
        return;
    }
 
    for (int next = cur + 1; next < v.size(); next++) {    
        vv.push_back(v[next]);
        sol(picked + 1, limit, next);
        vv.pop_back();
    }
}
 
int main() {
    cin >> n >> k;
 
    v.resize(n);
    for (int i = 0; i < n; i++)
        cin >> v[i];
 
    sort(v.begin(), v.end());    // next_permutation 을 위해서 미리 정렬을 한 번 해준다. 
                                // 이를 해주지 않으면 모든 순서 조합을 시뮬레이션 해볼 수 없다.
    sol(0, k, -1);    
    cout << st.size();
}