BOJ 5568 카드 놓기

https://acmicpc.net/problem/5568

5568번: 카드 놓기

재귀를 이용해 모든 경우의 수를 구하고, 이를 set에 넣어 해결했다. 

 

호출 stack 깊이(cnt)는 K, X는 수열에 추가할 수가 된다. backtrack 된 위치에서 방문했던 위치를 방문하지 않았다고 바꾸면 다음 loop의 재귀 호출에서 다시 사용될 수 있다. 위와 같은 방법으로 K가 3인 모든 수의 조합을 생성할 수 있고, 이를 std::set에 넣으면 중복 없는, 생성 가능한 모든 수의 개수를 구할 수 있다.

 

코드는 다음과 같다.

#include <iostream>
#include <string>
#include <set>
using namespace std;
int a[11], N, K;
bool visited[11];
set<string> comb;

auto P(int x, int cnt, string s) {
    if (cnt == K) return comb.insert(s); // k개 선택하면 끝
    for (int i = 0; i < N; i++) { // 선택 가능한 모든 원소에 대해
        if (!visited[i]) { // 이전에 선택된 원소는 다시 선택 안하도록
            visited[i] = true; // 현재 선택한 원소 방문 체크
            P(i, cnt + 1, s + to_string(a[i])); // cnt 증가하고 생성한 문자열에 추가
            visited[i] = false; // backtrack된 위치에서 선택했던 원소 방문 취소
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> N >> K;
    for (int i = 0; i < N; i++) cin >> a[i];
    P(0, 0, "");
    cout << comb.size();
}

 확장이 쉬운 string을 이용해 수를 관리했다.

 

 

---

dp & 조합 관련 문제들에서 자존감이 박살나는 바람에 이틀 가까운 시간 동안 kaggle, 모두의 딥러닝 강의 들으며 요양했다...