[백준] 15663 N과 M (9) c++

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

15663번: N과 M (9)

문제접근 및 풀이

기본적인 백트래킹문제이다.

 

고려해야할 사항이 몇가지 있다.

1. 사전 순으로 증가하는 순서로 출력해야 한다.

-> input 배열을 sort하고 백트래킹시에 0번 인덱스부터 접근한다.

 

2. 중복된 경우를 허용하지 않는다.

-> mul이라는 변수를 사용해서 바로 이전에 선택한 숫자를 저장하여 for문 안에서 mul과 겹친다면 넘어가도록 하여 중복을 없앤다.

 

3. 각 숫자는 한번만 사용가능하다.(N개의 자연수 중 M개의 숫자를 뽑는 경우이기 때문이다.)

-> v배열을 두어 check를 하며 백트래킹을 진행한다.

 

 

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

using namespace std;

int n,m;
vector<int> input;
vector<int> result;
int v[8]={0};

void bt(int depth){
  if(depth==m){
    for(int i=0; i<result.size(); i++){
      printf("%d ", result[i]);
    }
    printf("\n");
    return ;
  }
  int mul = -1;
  for(int i=0; i<n; i++){
    if(v[i]==1 || mul == input[i]) continue;
    mul = input[i]; 
    v[i]=1;
    result.push_back(input[i]);
    bt(depth+1);
    v[i]=0;
    result.pop_back();
  }
  return ;
}

int main(){
  cin >> n >> m;
  for(int x,i=0; i<n; i++){
    scanf("%d", &x);
    input.push_back(x);
  }
  sort(input.begin(), input.end());
  bt(0);
  return 0;
}