[백 트래킹] BOJ 15651 N과 M (3)

www.acmicpc.net/problem/15651

15651번: N과 M (3)

문제 해결 알고리즘

 

이 문제는 N과 M (1), (2)과 달리 next_permutation으로 구현하기 어렵다. 그러므로 이제부터 제대로된 백 트래킹 알고리즘으로 구현을 해야한다.

 

1. N과 M 값을 입력을 받은 다음 dfs()함수를 실행해준다.

 

2. dfs 함수에서 만약 n이 M과 같다면 배열(arr)에 있는 수들을 모두 출력해주고, 

   같지 않다면 배열에 숫자들을 1에서 N까지 순서대로 넣고 dfs함수에 n+1 값을 파라미터로 넣어준다.

 

소스 코드

 

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

int N,M;
int arr[8];

void dfs(int n){
  if(n == M){
    for(int i=0;i<M;i++){
      cout << arr[i] << " ";
    }
    cout << "\n";
    return;
  }
  for(int i=1;i<=N;i++){
    arr[n] = i;
    dfs(n+1); 
  }
}

int main(){
  cin >> N >> M;

  dfs(0);

}