[ BOJ / C++ ] 15665번 N과 M (11)

이번 문제는 백트레킹 알고리즘을 활용하여 해결하였다. 문제의 조건없이 출력하는 것은 쉽지만 같은 수를 여러 번 골라도 되지만 길이M의 수열끼리는 중복을 허용하지 않는다는 조건에서 생각이 필요했다.

• bool형 num_chk 배열을 통해 입력된 값이 존재하는지 확인한다.
• 만약 입력된 값이 존재한다면 arr 벡터에 넣지 않고, 존재하지 않을 때만 벡터에 push_back해준다. 이는 수열의 중복을 제거하는 역할을 한다.
• arr을 오름차순으로 정렬해준다. 이는 결과 출력이 오름차순으로 형성되기 위함이다.
• 같은 수를 여러 번 골라도 되기 때문에 DFS 함수 내에서는 따로 조건을 넣어주지 않는다.
• 변수 cnt로 result 배열의 인덱스(DFS의 깊이)를 나타내므로 result에 값을 넣을 때마다 cnt값을 증가시킨다.
• 만약 cnt가 m과 크기가 같아지면 result배열을 출력한다.

#include <iostream>
#include <algorithm>
#include <vector>
#define MAX 8
using namespace std;

int n, m, a;
vector<int> arr;
int result[MAX];
bool num_chk[10001];

void Input(){
    cin>>n>>m;
    for(int i=0; i<n; i++){
        cin>>a;
        if(!num_chk[a]){
            arr.push_back(a);
            num_chk[a]=true;
        }
    }
    sort(arr.begin(), arr.end());
}

void DFS(int cnt){
    if(cnt==m){
        for(int i=0; i<m; i++){
            cout<<result[i]<<" ";
        }
        cout<<"\n";
        return;
    }
    for(int i=0; i<arr.size(); i++){
        result[cnt]=arr[i];
        DFS(cnt+1);
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    Input();
    DFS(0);
    return 0;
}

처음에는 DFS 안에서 중복을 제거하려다가 시간초과가 발생하였고, 이를 입력 과정에서 제거하는 방식으로 변경하여 시간을 단축시켰다.