[백준 5568번] 카드 놓기 (C++)

문제링크 : https://www.acmicpc.net/problem/5568

5568번: 카드 놓기

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = INT_MAX;

int N, K, arr[11];
bool check[11];
set<int>result;

void func(int cnt, string s)
{
    if(cnt == K) 
    {
        result.insert(stoi(s)); //중복제거
        return;
    }

    for(int i=0; i<N; i++)
    {
        if(check[i]) continue;
        check[i]=1;
        string tmp = s; //현재 문자열 기준으로 추가
        tmp += to_string(arr[i]);
        func(cnt+1, tmp);
        check[i]=0;
    }
}

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

    cin >> N >> K;
    for(int i=0; i<N; i++) cin >> arr[i];

    func(0, "");    

    cout << result.size();
    return 0;
}

 

숫자를 가로로 추가해서 새로운 수를 만들기에 이를 문자열로 처리해준다.

따라서 K를 위한 카운팅과 문자열을 같이 재귀로 넘겨주며 백트래킹을 실시한다.

 

기존 입력받은 문자열을 기준으로 현재 인덱스에 위치한 배열의 값을 문자열로 바꿔서 더해주고, 이를 재귀로 넘겨준다.

처음 해당 인덱스에 대한 값을 chcek하고 이어서 재귀로 탐색후, 기존 인덱스의 check를 풀어서 다른 케이스를 찾도록 해준다.

 

문제의 예시로 봤듯이, (2, 1, 13 / 21, 1, 3) 중복 케이스가 발생할 수 있기 때문에 합해진 문자열을 set에 담아 저장하고, set의 크기를 출력해주었다.