[BOJ / C++] 5568번 : 카드 놓기

문제

상근이는 카드 n(4 ≤ n ≤ 10)장을 바닥에 나란히 놓고 놀고있다. 각 카드에는 1이상 99이하의 정수가 적혀져 있다. 상근이는 이 카드 중에서 k(2 ≤ k ≤ 4)장을 선택하고, 가로로 나란히 정수를 만들기로 했다. 상근이가 만들 수 있는 정수는 모두 몇 가지일까?

예를 들어, 카드가 5장 있고, 카드에 쓰여 있는 수가 1, 2, 3, 13, 21라고 하자. 여기서 3장을 선택해서 정수를 만들려고 한다. 2, 1, 13을 순서대로 나열하면 정수 2113을 만들 수 있다. 또, 21, 1, 3을 순서대로 나열하면 2113을 만들 수 있다. 이렇게 한 정수를 만드는 조합이 여러 가지 일 수 있다.

n장의 카드에 적힌 숫자가 주어졌을 때, 그 중에서 k개를 선택해서 만들 수 있는 정수의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 n이, 둘째 줄에 k가 주어진다. 셋째 줄부터 n개 줄에는 카드에 적혀있는 수가 주어진다.

출력

첫째 줄에 상근이가 만들 수 있는 정수의 개수를 출력한다.

Solved.ac 레벨

실버 IV

풀이

문제 태그에서는 브루트포스 알고리즘으로도 소개되고 있는데 나는 백트래킹을 연습하고 싶었던지라 백트래킹으로 풀어보았다.

단순히 카드 목록에서 DFS의 depth가 k가 되면 수를 카운팅해주면 된다고 생각했는데, 문제에서 중복에 관한 이야기가 나왔다.

한 정수를 만드는 조합이 여러 개 일수도 있다는 것. 하지만 카드를 조합해서 한 정수 2113을 만들었을 때, 이것이 21, 1, 3을 이용한 것인지 2, 1, 13을 이용한 것인지 알 수는 없다. 따라서 중복을 제거해주어야 한다.

 

따라서 C++의 자료형 중 하나인 set을 활용했다.

set은 key-value 형태의 map에서 value를 제거한 형태라고 보면 된다. key는 독립적인 값을 가져야 하므로, 중복이 제거된다.

따라서 DFS를 돌리며 백트래킹을 해 k장의 카드를 뽑아 정수를 만든 뒤 이 정수를 set에 담아 같은 값을 가지는 경우를 제거해준 뒤 이 set의 사이즈를 출력해주면 답이 된다.

Code

#include<bits/stdc++.h>

using namespace std;

int n, k;
int card[11];
bool visited[11];
set<string> tmp;

void DFS(string number, int depth) {
    if(depth == k) {
    	//카드를 k장 뽑아서 정수를 다 만들었다면 set에 담아준다.
        tmp.insert(number);
        return;
    } else {
        for(int i = 0; i < n; i++) {
            if(!visited[i]) {
                visited[i] = true; // i번째 카드 사용 처리
                DFS(number + to_string(card[i]), depth + 1); //depth개까지의 카드를 사용한 정수와 depth + 1을 넘겨 재귀호출.
                visited[i] = false; // 다음 번 탐색을 위해 i번째 카드 미사용 처리.
            }
        }
    }
}

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

    cin >> n >> k;

    for(int i = 0; i < n; i++) {
        cin >> card[i];
    }

    DFS(to_string(card[0]), 0);

    cout << tmp.size() << "\n";
    //카드를 k장 뽑아 정수를 만드는 경우가 담긴 set의 사이즈를 출력.

    return 0;
}

5568번: 카드 놓기