[백준/c++] 5568번: 카드 놓기

 

 

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

5568번: 카드 놓기

 

n개 중 k개를 선택해야 한다. 이런 문제는 백트래킹으로 하면 된다.

이 문제는 같은 숫자의 카드가 여러 개여도 중복 숫자를 선택할 수 있다. (같은 카드를 중복 선택은 안됨)

그런데, 그 숫자들로 만들어진 정수가 중복되면 안 된다. 

만든 정수가 중복되면 안되니까 간단하게 set를 사용할 수 있다. set 꼭 기억하기!!^^

 

#include <iostream>
#include <algorithm>
#include <string>
#include <set>
using namespace std;
int n, k, arr[11];
set<int> num;
bool ch[11];

void backtracking(int cnt, string s){
    if(cnt == k){
        num.insert(stoi(s)); //중복은 알아서 제거
        return;
    }
    
    for(int i=0; i<n; i++){
        if(!ch[i]){
            ch[i] = true;
            string ss = s + to_string(arr[i]);
            backtracking(cnt+1, ss);
            ch[i] = false;
        }
    }
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> k;
    for(int i=0; i<n; i++) cin >> arr[i];
    sort(arr, arr+n);
    
    backtracking(0, "");
    
    cout << num.size() << '\n';
    return 0;
}