백준 15663번, N과 M (9)

백준 15663번 c++ 문제풀이

문제:

백준 15663

풀이:

1. 백트레킹으로 접근하기. 재귀함수 만들기
2. 수열을 만들되 중복된 수열을 만들면 안된다. 그래서 dfs처럼 재귀로 모든 숫자를 확인하지만, 수열의 마지막 요소만 다른지 확인하여 중복을 방지한다.
3. arr[]에 선택한 수를 저장한다고 하면, 변수 comp에 저장된 arr[]의 값을 넣어준다.
4. 따로 저장해주는 이유는 함수를 진행하면 arr[]의 값이 계속 변하기 때문이다.

코드:

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int arr[9];

void back(vector<int> v, bool isvisited[], int m, int cnt){

    if(cnt == m){
        for(int i=0;i<m;i++){
            cout << arr[i] << " ";
        }
        cout << "\n";
    }else{
        int comp = 0;
        for(int i=0;i<v.size();i++){
            if(!isvisited[i] && v[i] != comp){//현재 고르려는 숫자가 방문하지 않은 숫자라면, 이전 수열의 마지막 숫자와 현재 고른 숫자가 다르면
                isvisited[i] = true; //현재 숫자 선택하기 
                arr[cnt] = v[i];//배열에 저장하기
                comp = arr[cnt]; // 이전 수열의 마지막 원소를 저장,
                cnt++; //카운트 증가 시키기.
                back(v, isvisited, m, cnt);//다음 숫자 고르기, 만약 현재 이미 m개를 골랐다면 이함수 시작시 출력하기
                cnt--;//카운트를 뒤로 물려서 새로운 수를 고르게 하기,
                isvisited[i] = false; //골랐던 숫자 안고른 수로 변경하기, 초기화하기
                
            }
        }
    }
}

int main(){

    int n, m;

    vector<int> v;

    cin >> n >> m;
    
    for(int i=0;i<n;i++){
        int input;

        cin >> input;

        v.push_back(input);
    }

    sort(v.begin(), v.end()); //정렬시켜준다.

    bool isvisited[n] = {0, };

    int cnt = 0;

    back(v, isvisited,m, cnt);
    return 0;
}

중복이 안되게 하는게 어려웠다. 수열의 마지막 수를 따로 저장해두는게 중요한거 같다. 감사합니다.