[백준 15663번] [Backtracking / Map] N과 M (9)

Approach

같은 숫자가 여러 개 들어갈 수 있음에도 불구하고, 중복되는 수열을 여러 번 출력하면 안되는 것이 이 문제의 가장 핵심이다.

이전 문제의 경우 단순히 해당 index 이후부터 고려하거나 처음부터 고려하는 방식으로 해결할 수 있으나, 이 문제의 경우에는 중복 때문에 단순히 그렇게 처리를 할 수 없다.

 

따라서 얼마까지 중복해서 사용할 수 있는지를 핸들링 하기 위해서 map 자료구조를 활용하였다.

capacity가 있으면 해당 index를 사용할 수 있는 느낌으로 해결해주면 된다.

 

추가적으로 같은 숫자때문에 중복되는 수열이 발생할 수 있는데, 이는 unique함수를 활용해서 해결해주면 된다.

상당히 어렵다..

Code

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

using namespace std;
map<int, int> cap;
int result[8];
vector<int> s;
vector<vector<int> > output;
int n, m;

void solve(int index, int cur){
    result[cur++] = s[index];
    cap[s[index]] -= 1;
    if(cur == m){
        vector<int> temp;
        for(int i = 0; i < m; i++){
           temp.push_back(result[i]);         
        }
        output.push_back(temp);
    }
    else{
        for(int i = 0; i < s.size(); i++){
            if(cap[s[i]] > 0){
                solve(i, cur);
            }
        }
    }
    cap[s[index]] += 1;

    return;
}

int main(void){
    fastio;
    cin >> n >> m;

    for(int i = 0; i < n; i++){
        int t;
        cin >> t;
        cap[t] += 1;
        s.push_back(t);
    }

    sort(s.begin(), s.end());
    s.erase(unique(s.begin(), s.end()), s.end()); // 중복 제거

    for(int i = 0; i < n; i++){
        solve(i , 0);
    }
    sort(output.begin(), output.end());
    output.erase(unique(output.begin(), output.end()), output.end());
    for(int i = 0; i < output.size(); i++){
        for(int j = 0; j < m; j++){
            cout << output[i][j] << " ";
        }
        cout << "\n";
    }
    return 0;
}