BOJ15649: N과 M(1)

작성일

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

  • 1월동안 100문제 풀기 (9/100)
  • 백트래킹 문제. 역시나 시키는대로 풀기
  • 다만 교훈을 얻은점이 있음: Next Permutation은 아래와 같은 Permutation 구하기 에서 Stack을 쓰는것을 따라하면 된다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <bits/stdc++.h>
using namespace std;

int M, N, mask[11];
vector<int> arr;

void go(int n) {
  if(n == N) {
    for(int n : arr) cout << n << " ";
    cout << "\n";
    return;
  }

  for(int i = 1; i <= M; i++) {
    if(mask[i]) continue;
    mask[i] = 1;
    arr.push_back(i);
    go(n+1);
    arr.pop_back();
    mask[i] = 0;
  }
}

int main() {
  cin >> M >> N;
  go(0);
}