[BOJ] 15663. N과M(9)

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

재귀를 사용해서 풀었습니다.

vector를 사용해서 넣어주고 빼주고 했습니다~

앞에 N과 M문제에 비해 난이도가 있는 문제였습니다.

같은 수열의 중복을 제거해야하는데,

전 같은 dpeth안에 같은 수가 나오지 않게하여 해결했습니다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n, m;
int arr[9];
bool ch[9];
int temp;
vector <int> v;
void go(int x, int cnt) {
    if (cnt == m) {
        for (int i = 0; i < m; i++) {
            cout << v[i] << ' ';
        }cout<<'\n';
        return;
    }
    int temp=false;
    for (int i = 1; i <= n; i++) {
        if (ch[i] == false&&temp!=arr[i]) {
            v.push_back(arr[i]);
            temp = arr[i];//같은 depth안에 더이상 arr[i]와 같은 수가 나오지 않도록 설정
            ch[i] = true;
            go(i, cnt + 1);
            ch[i] = false;
            v.pop_back();
        }
    }
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> arr[i];
    sort(arr, arr + n + 1);
    go(1, 0);
}

혼잣말

앞에 N과M은 그냥 후딱 풀었는데,
갑자기 날 당황시켰다…
이런 방법은 다른 문제를 풀때도 유용할 것 같다.