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인 경우들의 최소 뒤집기 횟수들을 미리 구해놓는다.

 

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

GitHub - sbl133/JongmanBook

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

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