[백 트래킹] BOJ 15649 N과 M (1)

www.acmicpc.net/problem/15649

15649번: N과 M (1)

알고리즘 문제 해결

 

이 문제는 매우 간단하게 c++에 있는 라이브러리인 next_permutation 함수를 이용하면 쉽게 풀 수 있는 문제였다. 이 문제에서 중요한 건 중복된 출력이 있으면 안되므로 팩토리얼 함수를 따로 만들어서 그만큼을 건너뛰고 출력한 것을 볼 수 있다. 그리고 또 M까지의 숫자만 출력하는 것도 포인트이다.

 

 

소스 코드

#include <bits/stdc++.h>
using namespace std;

int pac(int x){
  int result = 1;
  while(x!=0){
    result *= x;
    x--;
  }
  return result;
}
int main(){
  
  int N, M; cin >> N >> M;
  vector<int> v(N);

  for(int i=0;i<N;i++){
    v[i] = i + 1;
  }

  do {

    for(int i=0;i<M;i++){
      cout << v[i] << ' ';
    }

    cout << '\n';

    for(int i=0;i< pac(N-M) - 1;i++) next_permutation(v.begin(), v.end());

  } while(next_permutation(v.begin(),v.end()));
}