오래된 디스크
시간 제한3초메모리 제한2048 MB
1부터 n까지의 순열(n은 10 이하)이 주어질 때, 네 구간으로 나눠 C, A, D, B 순서로 바꾸는 연산으로 정렬하는 최소 횟수를 구합니다.
문제
키 1.83미터, 몸무게 80킬로그램인 산드라 엘카세비치(구 성 페르코비치)는 크로아티아의 육상 선수다. 올림픽 금메달을 2회, 세계선수권 우승을 2회, 유럽선수권 우승을 7회 했고, 원반던지기 크로아티아 기록 보유자다.
말나르 씨는 키는 거의 같지만 체중은 훨씬 나간다. 크로아티아 정보학회 사무총장이며, 공식 기록상 국제정보올림피아드 크로아티아 대표단으로 24회 참가했다(실제로는 25회). 1992년 파스칼 부문 국내 챔피언이었다. 또한 오래된 디스크, 즉 플로피 디스크를 던지는 기록의 크로아티아 보유자다.
말나르 씨는 여행에서 좋은 와인이나 매운 소스를 사 오면 붐비는 사무실에 자리를 만들어야 한다. 그럴 때면 오래된 플로피 디스크 뭉치를 집어 쓰레기통에 버린다. 이번에는 n장의 디스크가 손에 잡혔다. 디스크에는 그가 가장 좋아하는 운영체제 MS Windows 95가 들어 있다.
디스크에는 설치할 때 넣는 순서대로 1부터 n까지 자연수가 적혀 있다. 말나르 씨는 이 디스크들이 준 즐거운 기억을 떠올리며, 1부터 n까지 정렬한 뒤에야 버리기로 했다.
먼저 디스크를 모두 한 줄로 늘어놓는다. 사용할 수 있는 연산은 하나뿐이며 이를 malnar-swap이라고 부른다. malnar-swap은 다음과 같이 진행된다.
- 전체 디스크 배열을 길이가 임의인 연속된 부분 배열(구간) 4개로 나눈다. 빈 부분 배열도 허용한다. 순서대로 A, B, C, D라고 이름 붙인다.
- 그다음 부분 배열들을 섞어서 새 배열이 C, A, D, B 순서가 되도록 한다.
디스크 배열을 1부터 n까지 정렬하는 데 필요한 malnar-swap 연산의 최소 횟수를 구하라. 서로 다른 malnar-swap에서 나누는 부분 배열의 길이는 같을 필요가 없다.
입력
첫 줄에 문제에 나온 자연수 n ()이 주어진다.
둘째 줄에는 디스크 배열의 초기 상태인 1부터 n까지 수의 순열이 주어진다.
출력
디스크 배열을 정렬하는 데 필요한 malnar-swap 연산의 최소 횟수를 한 줄에 출력한다.
힌트
첫 번째 예제 설명:
두 번째 예제 설명:
