큐 정렬하기
시간 제한8초메모리 제한512 MB
빈 스택 두 개를 이용해 큐에 든 0부터 N-1까지의 숫자를 오름차순으로 정렬하는 데 필요한 연산 횟수의 최솟값을 구합니다.
문제
큐 Q와 스택 A, B가 있고, 각각에 대해 다음 연산을 정의한다.
QA(n): Q에서 원소를 dequeue하여 A에 push한다. 이를 n번 반복한다.QB(n): Q에서 원소를 dequeue하여 B에 push한다. 이를 n번 반복한다.QQ(n): Q에서 원소를 dequeue하여 다시 Q에 enqueue한다. 이를 n번 반복한다.AQ(n): A에서 원소를 pop하여 Q에 enqueue한다. 이를 n번 반복한다.BQ(n): B에서 원소를 pop하여 Q에 enqueue한다. 이를 n번 반복한다.AB(n): A에서 원소를 pop하여 B에 push한다. 이를 n번 반복한다.BA(n): B에서 원소를 pop하여 A에 push한다. 이를 n번 반복한다.
각 연산은 n의 값과 관계없이 한 번의 연산으로 센다. dequeue는 큐의 맨 앞 원소를 꺼내는 것이고, enqueue는 큐의 맨 뒤에 원소를 추가하는 것이다. 스택의 push와 pop은 모두 맨 위에서 이루어진다.
Q에 여러 개의 수가 들어 있고 A와 B는 비어 있다고 하자. 큐에 같은 수들이 오름차순으로 저장되도록 만드는 데 필요한 연산의 최솟값을 구하라. 예를 들어, 맨 앞이 4인 큐 (4 3 1 2 0)은 QA(2), QQ(2), AQ(2) 세 번의 연산으로 정렬할 수 있다. 큐 (5 4 1 3 2 0)은 QB(2), QQ(1), QB(2), BQ(4) 네 번의 연산으로 정렬할 수 있다.
주어진 큐를 정렬하는 데 필요한 연산의 최솟값을 구하는 프로그램을 작성하라.
입력
입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 한 줄에 (N + 1)개의 정수로 주어진다. 첫 번째 정수는 큐의 원소 개수 N이다. 큐에는 0부터 (N - 1)까지의 정수가 임의의 순서로, 앞에서부터 뒤 순서로 들어 있다. 큐의 원소는 최대 10개이다.
입력의 끝은 정수 N = 0만 담긴 줄이다. 이 줄은 테스트 케이스에 포함되지 않는다.
출력
각 테스트 케이스마다 결과를 한 줄에 출력한다.