algospot Sorting Game(문제 ID: SORTGAME) c++

알고스팟 문제 링크: https://algospot.com/judge/problem/read/SORTGAME

algospot.com :: SORTGAME

중복이 없는 정수 수열에 임의의 구간을 선택해서 뒤집는 작업을 반복하여 수열을 정렬시킨다 했을때 필요한 최소 뒤집기 횟수를 구하는 문제이다.

 

상대적 크기가 같은 배열의 최소 뒤집기 횟수는 같다.

예를들어 {1, 3, 2, 4}와 {10, 30, 20, 40}의 최소 뒤집기 횟수는 같다. 따라서 크기가 n인 수열은 원소가 1~n인 경우만 고려하면 된다.

수열의 배치가 다른 각각의 경우의 수는 n!이므로 n!개의 정점과 현재 상태에서 뒤집기 한번 했을때의 수열이 서로 연결된 형태의 그래프를 이용하여 문제를 풀 수 있다.

이때 테스트케이스의 최대가 1000이므로 크기가 1~n인 경우들의 최소 뒤집기 횟수들을 미리 구해놓는다.

 

	#include<iostream>
	#include<vector>
	#include<map>
	#include<queue>
	#include<algorithm>
	using namespace std;
	// toSort[vector] = vector를 정렬시키는데 필요한 뒤집기 횟수
	map<vector<int>, int> toSort;
	// 크기가 n인 배열이 배치될수 있는 모든 경우의 뒤집기 횟수 계산
	void precalc(int n) {
	vector<int> perm(n);
	for (int i = 0; i < n; i++)
	perm[i] = i;
	queue<vector<int>> q;
	q.push(perm);
	toSort[perm] = 0;
	while (!q.empty()) {
	vector<int> here = q.front();
	q.pop();
	// 현재 비용
	int cost = toSort[here];
	// 모든 뒤집기 상황 고려
	for(int i=0; i<n; i++)
	for (int j = i + 2; j <= n; j++) {
	reverse(here.begin() + i, here.begin() + j);
	// 배열을 뒤집었을때 아직 계산이 안된 배열이면
	if (toSort.count(here) == 0) {
	// 현재 배열 비용에 +1
	toSort[here] = cost + 1;
	q.push(here);
	}
	// 배열 원상복구
	reverse(here.begin() + i, here.begin() + j);
	}
	}
	}
	// 상대적 크기만 고려하면 되므로 입력으로 주어진 perm을 정규화 시킨후 toSort에서 찾기
	int solve(const vector<int>& perm) {
	int n = perm.size();
	vector<int> fixed(n);
	for (int i = 0; i < n; i++) {
	int smaller = 0;
	for (int j = 0; j < n; j++)
	if (perm[j] < perm[i])
	smaller++;
	fixed[i] = smaller;
	}
	return toSort[fixed];
	}
	int main() {
	for (int i = 1; i <= 8; i++)
	precalc(i);
	int testcase;
	cin >> testcase;
	while (testcase--) {
	int n;
	cin >> n;
	vector<int> v;
	int tmp;
	for (int i = 0; i < n; i++) {
	cin >> tmp;
	v.push_back(tmp);
	}
	cout << solve(v) << endl;
	}
	}

view raw algospot Sorting Game(문제 ID: SORTGAME).cpp hosted with ❤ by GitHub

코드 원본: https://github.com/sbl133/JongmanBook/blob/main/29.%20BFS/SORTGAME.cpp

GitHub - sbl133/JongmanBook

댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!

reference: 프로그래밍 대회에서 배우는 알고리즘 문제해결전략2