백준 10972 다음 순열, 이전 순열, 모든 순열

요즘 백트래킹, 브루트포스 부분을 공부하고 있는 상황에서 순열 3총사를 만났다.

"다음 순열"의 경우 백트래킹을 활용해 모든 조합을 만들어 가다, 입력으로 준 숫자를 찾으면 그 다음번에 오는 조합을 답으로 출력하는 방식을 사용하였는데, 시간 초과가 났다. 알고보니 이렇게 하는게 아니더라. 다른 방법이 있는데, 백트래킹 같은 개념을 사용하지 않는 단순 수학문제 였다.

"모든 순열" (10974) 문제가 내가 "다음 순열" 문제를 풀 때 만든 백트래킹 코드를 그대로 사용하면 답으로 나왔다.

 

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

using namespace std;

int n;
int flag = 0;
vector<int> givens;
int isused[10002];
int pack[10002];

void func(int cnt)
{
  if (cnt == n) // 4개 다 채웠으면
  {
    for (int i = 0; i < n; i++)
    {
      cout << pack[i] << " ";
    }
    cout << "\n";
  }

  for (int i = 1; i <= n; i++)
  {
    if (isused[i] == 0)
    {
      isused[i] = 1;
      pack[cnt] = i;
      func(cnt + 1);
      pack[cnt] = 0;
      isused[i] = 0;
    }
  }
}

int main()
{
  cin >> n;
  
  func(0);
  if (flag == 1)
    cout<<-1<<"\n";
  return 0;
}

수정도 거의 하지 않고 출력하도록 바꿨다. isused, pack 도 사실 나눌 필요가 없는데, 다음번에는 없이 만들어야겠다.