[BOJ] 5568 - 카드 놓기

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

5568번: 카드 놓기

 

난이도

DFS, SET / 난이도 ⭐️ / 15분

 

문제풀이

dfs와 set을 활용하면 된다.

카드의 개수 n, 선택하는 카드의 개수는 k로 n은 최대 10 k는 최대 4이다. 

최악의경우 10*9*8*7로 dfs로 풀어도 될 것 같다.

 

모든 순열을 구하는 시간복잡도는 O(n!)이다.

궁금해서 찾아보니 n이 10을 조금만 초과해도 모든 순열 조합을 구하면 시간초과가 날 수 있다고 한다. 

11!이 3천얼마인 반면에 12!부터는 4억얼마이고 13!부터는 62억이다.

#include <iostream>
#include <vector>
#include <string>
#include <set>
using namespace std;

set<int> s;
void dfs(vector<int> &v, string str, int max_count, int cur_count)
{

    if (cur_count == max_count)
    {
        s.insert(stoi(str));
        return;
    }

    int temp;
    for (int i = 0; i < v.size(); i++)
    {
        if (v[i] == -1)
            continue;

        temp = v[i];

        v[i] = -1;
        dfs(v, str + to_string(temp), max_count, cur_count + 1);
        v[i] = temp;
    }
}

//순열 , set
int main()
{
    int n, k, temp;
    vector<int> v;

    cin >> n;
    cin >> k;
    for (int i = 0; i < n; i++)
    {
        cin >> temp;
        v.push_back(temp);
    }

    dfs(v, "", k, 0);
    cout << s.size() << "\n";
}