[백준] 15655번 N과 M (6) (C++) - backtracking

문제

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

15655번: N과 M (6)

코드

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

using namespace std;

int n, m;
vector<int> v;
int arr[9];
bool isVisited[9];

void dfs(int num, int cnt){
  if(cnt == m){
    for(int i=0; i<m; i++){
      cout << arr[i]<< ' ';
    }
    cout << '\n';
    return;
  }
  for(int i=num; i<n; i++){
    if(!isVisited[i]){
      isVisited[i] = true;
      arr[cnt] = v[i];
      dfs(i+1, cnt+1);
      isVisited[i] = false;
    }
  }
}

int main(){
  cin >> n >> m;
  for(int i=0; i<n; i++){
    int a;
    cin >> a;
    v.push_back(a);
  }
  sort(v.begin(), v.end());
  dfs(0, 0);
  return 0;
}

 

++

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

using namespace std;

int n, m;
vector<int> v;
int arr[9];

void dfs(int num, int cnt){
  if(cnt == m){
    for(int i=0; i<m; i++){
      cout << arr[i]<< ' ';
    }
    cout << '\n';
    return;
  }
  for(int i=num; i<n; i++){
    arr[cnt] = v[i];
    dfs(i+1, cnt+1);
  }
}

int main(){
  cin >> n >> m;
  for(int i=0; i<n; i++){
    int a;
    cin >> a;
    v.push_back(a);
  }
  sort(v.begin(), v.end());
  dfs(0, 0);
  return 0;
}

정리

이 문제와 15650번의 차이점은 15650번은 수열 원소의 범위를 1부터 N까지 범위를 지정한 반면 이 문제는 서로 다른 원소 N개를 입력받는다. 즉 15650번 코드에서 N개의 원소들을 입력받고 오름차순으로 정렬해주는 코드를 작성하면 해결할 수 있다.

 

++ 15650번과 같이 방문체크(isVisited)를 할 필요가 없었다.

참조

https://kdongree.tistory.com/81