[BOJ 10974]

문제 바로가기 : https://www.acmicpc.net/problem/10974
문제 설명은 위 링크에서 확인해주시길 바랍니다.

solution

review

N이 입력됐을 때 1~N의 순열을 내림차순부터 오름차순까지 모두 출력하면 된다.
해당 숫자가 입력됐는지 여부를 확인하기 위해 bool 타입의 chk[]를, 숫자를 담는 배열 arr을 선언하고 시작한다.
cnt는 숫자가 얼마나 담겼는지 카운트하기도 하지만, 가장 최근에 담긴 숫자를 지우기 위해 사용된다.

for (int i = 1; i <= n; i++) {
    if (chk[i]) continue;
    cnt++;
    arr.push_back(i);
    chk[i] = true;
    dfs(i);
    chk[i] = false;
    cnt--;
    arr.erase(arr.begin() + cnt); //이 부분!
}

순열이기 때문에 기본적으로 DFS를 통해서 값을 저장한다. 입력값 N과 담은 숫자 개수 cnt가 같아지면 출력한다.

void dfs(int a) {
  if (cnt == n) {
      for (int i = 0; i < n; i++) cout << arr[i] << " ";
      cout << '\n';
      return;
  }
  ...
}

처음엔 실시간으로 출력하려고 구현을 하다가 생각보다 잘 안돼서 방법을 바꿨다.
실제로 구현이 되는진 모르겠지만 이 방법이 제일 깔끔한 것 같다.
C++로 푼다면 next_permutation()을 이용해도 된다.