5000번 : 빵정렬

https://www.acmicpc.net/problem/5000

 

 

일행중 누군가가 swap에서 parity라는 의문을 제기하자. 나는 데이터 통신에서 패리티체크는 들어봤지만 다른 식으로 쓰이는 걸 처음봐서 이 문제를 추천(?) 받게 되었다.

 

해당 문제의 경우에는 인접한 수열 3개를 선택해서 A B C 일때 C A B 로 만들 때 수열 A로 수열 B로 만들 수 있느냐 없느냐를 뭇는 문제이다. 하나씩 swap 하는 문제들은 여럿 있지만 이러한 형태는 처음 보는 것이었다. 

 

여기서 "순열의 홀짝성" 이라는 개념이 나온다. 특정한 순열을 1:1로 교환해서 증가하는 순으로 만드는데 N번의 시행횟수가 있을 수 있지만 해당 N의 홀, 짝 여부는 항상 동일하다 라는 것이다. 21345라는 순열을 봤을 때 12345로 만들려면 1번, 3번, 5번 등의 홀수 횟수로 증가하는 것이다.

 

해당 문제도 이 개념을 이용하면, 순열의 inversion count개수를 세서 순열의 홀짝성을 비교해보면 가능한지 불가능한지를 알 수가 있다. 나같은 경우는 inversion count를 세그트리를 이용하여 구현하였다. 확률과 통계에 있는 개념이라는데 나는 처음들어 보는 것이라서 조금 생소했다.