[BOJ/5568번카드놓기] c++ / backtracking

문제

주어진 N개의 카드 중 K장을 골라 만들 수 있는 숫자의 개수를 구하는 문제

 

생각

백트래킹 사용해서 나올 수 있는 카드 조합을 구한 뒤 중복되는 수는 삭제해야겠다 생각함

 

문제풀이

1.cnt가 K개가 되면, r배열에 있는 카드로 숫자 num을 만듦

1-1.res 벡터 배열에 num을 넣어줌

2.0부터 N까지 사용하지 않은 카드가 나오면

2-1.사용표시 + r배열에 저장

2-2.func(cnt+1)

2-3.사용표시 삭제

3.res배열 정렬 후 중복되는 원소 삭제

4.res.size 출력

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int N, K;
int arr[11], r[5], isused[11];
vector<int> res;
void func(int cnt) {
  if ( cnt == K ) {
    int num = 0;
    for ( int i = 0; i < K; i++ ) {
      if ( r[i] > 9 )
        num = num*10;
      num = num*10 + r[i];
    }
    res.push_back(num);
    return;
  }

  for ( int i = 0; i < N; i++ ) {
    if ( !isused[i] ) {
      isused[i] = 1;
      r[cnt] = arr[i];
      func(cnt+1, i);
      isused[i] = 0;
    }
  }
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  
  cin >> N;
  cin >> K;
  for ( int i = 0; i < N; i++ ) cin >> arr[i];
  func(0);

  sort(res.begin(), res.end());
  res.erase(unique(res.begin(), res.end()), res.end());
  cout << res.size();
}