Sorting Game 알고스팟

문제 : https://algospot.com/judge/problem/read/SORTGAME

문제

중복이 없는 정수 수열이 주어진다. 이 때, 우리는 이 수열의 임의의 구간을 선택해서 해당 구간을 뒤집을 수 있다. 이 뒤집기 연산을 통해 전체 수열을 정렬하고 싶다. 그런데, 같은 수열도 두 가지 이상의 방식으로 정렬할 수 있다. 예를 들어 3 4 1 2 는, 3 4 와 1 2 를 각각 뒤집어 4 3 2 1 을 만든 뒤, 전체를 뒤집어 정렬할 수도 있지만, 4 1 2 를 먼저 뒤집고, 3 2 1 을 다시 뒤집으면 두 번만의 연산으로 정렬할 수도 있다.

정렬을 위해 뒤집기 연산을 최소 몇 번 해야 하는지를 계산하는 프로그램을 작성하라.

코드 ( C++ ) 종만북 참조

#include <iostream>

#include <map>

#include <vector>

#include <algorithm>

#include <queue>

using namespace std;

map<vector<int>, int> dis;

// [0, .. n-1]의 모든 순열에 대해 계산해 저장한다.

void precalc(int n)

{

// 0 1 2 3 .. n-1 의 배열로 초기화

vector<int> perm(n);

for (int i = 0; i < n; ++i) perm[i] = i;

queue<vector<int>> q;

q.push(perm);

dis[perm] = 0;

while (!q.empty())

{

vector<int> here = q.front();

q.pop();

int cost = dis[here];

// i 이상 i+2 인덱스 사이의 배열을 뒤집는다.

for (int i = 0; i < n; ++i)

{

for (int j = i + 2; j <= n; ++j)

{

reverse(here.begin() + i, here.begin() + j);

// 방문한적이 없다면 방문

// 너비우선 탐색이기에 자동으로 가장 짧은 경로가 저장된다.

if (dis.count(here) == 0)

{

dis[here] = cost + 1;

q.push(here);

}

reverse(here.begin() + i, here.begin() + j);

}

}

}

}

int solve(vector<int>& perm)

{

int n = perm.size();

vector<int> temp(n, 0);

// temp 배열을 [0 .. n-1]의 순열로 바꾼다.

for (int i = 0; i < n; ++i) {

int smaller = 0;

for (int j = 0; j < n; ++j)

{

if (perm[j] < perm[i])

smaller++;

}

temp[i] = smaller;

}

return dis[temp];

}

int main()

{

int C;

cin >> C;

while (C--)

{

int n;

cin >> n;

vector<int> v(n, 0);

for (int i = 0; i < n; ++i)

cin >> v[i];

precalc(n);

cout << solve(v) << "\n";

}

return 0;

}