백준 15664번: N과 M (10)

백준 15664번: N과 M (10)

15664번: N과 M (10)

 

N과 M (9)를 풀었다면 10은 금방 풀 수 있다고 하는데 나는 (9)를 푼지 2달이 넘어서 기억이 잘 나지 않았다. 아무튼 기억을 되살려보고자 이것저것 하다가 9보다 더 간단하게 풀게되었다. 코드도 기존 N과 M시리즈에서 몇줄 추가되지 않았다. 

 

이전에 삽입했던 값을 기억하는 prev 변수를 만들었고, 만일 다음에 들어가야하는 수가 prev값과 같다면 그 수는 생략. 비내림차순으로 정렬된 상태로 답을 출력하기 때문에 prev를 사용할 수 있었다. 예를들어 M이 2이고 입력된 값이 1 9 9라고 가정했을 때 1을 vector에 push, prev에 1을 저장한다. 9를 push 후 prev에는 9를 저장. 함수 백트랙킹을 하고 다음 숫자를 봤는데 또 9이다. 이 때 prev에 9가 저장되어 있기 때문에 이 9는 생략을하게 된다.

 

말로 하면 어려우니까 직접 코드로 보는 것이 낫다.

 

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int n, m;
int arr[9];
vector<int> v;
void dfs(int a){
    if(v.size() == m){
        for(int i = 0; i < m; i++){
            cout << v[i] << " ";
        }
        cout << "\n";
        return;
    }
    int prev = 0;
    for(int i = a; i < n; i++){
        if(prev == arr[i]) continue;
        v.push_back(arr[i]);
        dfs(i+1);
        prev = arr[i];
        v.pop_back();
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for(int i = 0; i < n; i++){
        cin >> arr[i];
    }
    sort(arr, arr+n);
    dfs(0);
    return 0;
}