BOJ 5568 카드 놓기

작성일 | In |

Problem : 카드 놓기

유형 : 순열

문제 해석

  • 카드를 조합하여 만들 수 있는 모든 경우를 중복없이 세어라

문제 재해석

  • 순서까지 고려해야 하므로 순열 문제이다.

해결 전략

  • permutation을 통해 모든 순열을 만들어 본다.

설계, 구현

  • 정렬을 한다.
  • next_permuation을 통해 모든 순열을 구해본다.

디버깅

  • 조합으로 착각 했었다.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <bits/stdc++.h>
using namespace std;

int n, k;
vector<int> nums;

unordered_map<string, bool> m;

void Solve() {
    int answer = 0;

    sort(nums.begin(), nums.end());
    do {
        string num = "";
        for (int i = 0; i < k; ++i) {
            num += to_string(nums[i]);
        }
        if (m[num]) continue;
        m[num] = true;
        answer++;
    } while (next_permutation(nums.begin(), nums.end()));

    cout << answer << "\n";
}

void Input() {
    cin >> n;
    cin >> k;

    nums.resize(n);
    for (auto& it : nums) {
        cin >> it;
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);  cout.tie(NULL);
    freopen("input.txt", "r", stdin);

    Input();
    Solve();

    return 0;
}

피드백

  • 비트마스킹을 이용해서 뽑는 방법은 조합으로 해결한다.
  • 하지만 이렇게 순서를 고려해야 하는 경우는 순열로 해결 해야 한다.