[ BOJ 5568 ] S4 카드 놓기 { C++ }

5568번: 카드 놓기

5568번: 카드 놓기

C++

• 뽑을 카드 개수에 따라 모든 경우의 수를 돌려야 하므로 백 트래킹.
• map은 중복 검사와 정렬까지 해주는데, 이 문제에서 정렬은 필요가 없으므로 대신 unordered_set, unordered_map을 써도 좋다.
• map<저장할 자료형, bool>은 set과 구조가 같다 카더라.

#include <iostream>
#include <map>
#include <vector>

using namespace std;

map<string, bool> M;
vector<int> DECK;
int N, P, cnt = 0;
bool USED[10];

void f(vector<int> V, int D)
{
    if (D == P)
    {
        string res = "";
        for (int k = 0; k < P; k++)
            res += to_string(DECK[k]);
        M[res] = 1;
        return;
    }
    for (int i = 0; i < N; i++)
    {
        if (!USED[i])
        {
            USED[i] = true;
            DECK.push_back(V[i]);
            f(V, D + 1);
            DECK.pop_back();
            USED[i] = false;
        }
    }
}

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

    cin >> N >> P;
    vector<int> V(N);

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

    f(V, 0);
    for (auto m : M)
        cnt++;
    cout << cnt;
}

 

unordered_set로 구현한 코드

#include <iostream>
#include <unordered_set>
#include <vector>

using namespace std;

unordered_set<string> US;
vector<int> DECK;
int N, P, cnt = 0;
bool USED[10];

void f(vector<int> V, int D)
{
    if (D == P)
    {
        string res = "";
        for (int k = 0; k < P; k++)
            res += to_string(DECK[k]);
        US.insert(res);
        return;
    }
    for (int i = 0; i < N; i++)
    {
        if (!USED[i])
        {
            USED[i] = true;
            DECK.push_back(V[i]);
            f(V, D + 1);
            DECK.pop_back();
            USED[i] = false;
        }
    }
}
3
int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N >> P;
    vector<int> V(N);

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

    f(V, 0);
    for (auto s : US)
        cnt++;
    cout << cnt;
}