팬케이크 정렬 Batch 컴파일 명령
| 시간 제한 | 메모리 제한 | 제출 횟수 | 통과한 사람 수 | 비율 |
|---|---|---|---|---|
| 1000 ms | 256 MiB | 55 | 15 | 27.27% |
여러분에게 스택 형태로 쌓여 있는 $N$ ($1 \le N \le 8$)개의 팬케이크가 주어졌습니다. 맨 밑과 맨 위의 팬케이크는 각각 $0$번과 $N-1$번이 붙어 있습니다. 팬케이크의 크기는 그것의 지름이며 양의 정수입니다. 모든 팬케이크들은 서로 다른 크기를 가지고 있습니다. 크기가 각각 3, 8, 7, 6, 10인 $N=5$개의 팬케이크로 구성된 A$는 아래와 같이 그려볼 수 있습니다.
4 (top) 10 3 6 2 7 1 8 0 (bottom) 3 ----------------------- index i A[i]
우리는 스택을 내림차순으로 정렬하고 싶습니다. 즉 가장 큰 팬케이크가 맨 밑에 있고 가장 작은 팬케이크가 맨 위에 있어야 합니다. 문제를 실제 생활과 가깝게 만들기 위해, 팬케이크를 정렬하는 것은 $flip(i)$로 나타낼 팬케이크 '뒤집기' 연산만으로 해야 합니다. $flip(i)$ 연산은 스택 안에 주걱을 넣고, $i$번부터 $N-1$번까지의 팬케이크를 들어 올린 뒤, 이들을 뒤집습니다. 그 결과, $i$번부터 $N-1$번 팬케이크의 위치는 뒤집힙니다.
예를 들어, 스택 A는 $flip(0)$ 연산을 통해 스택 B로 전환될 수 있습니다. (주걱을 넣어서 0번부터 4번까지의 팬케이크를 뒤집습니다.) 스택 B는 $flip(3)$을 통해 스택 C로 전환될 수 있습니다. 스택 C는 $flip(1)$을 통해 스택 D로 전환될 수 있습니다. 우리의 목표는 이 스택을 스택 E와 같이 내림차순 정렬하되, 뒤집는 횟수를 최소화하고자 합니다.
4 (top) 10 <-- 3 <-- 8 <-- 6 3 3 6 8 <-- 3 7 ... 6 2 7 7 7 3 7 1 8 6 6 <-- 8 8 0 (bottom) 3 <-- 10 10 10 10 -------------------------------------------------------------- index i A[i] B[i] C[i] D[i] ... E[i]
빌 게이츠 (Microsoft 창업자, 전 CEO, 최근 의장)은 지금껏 단 하나의 연구 논문을 썼는데, 이것은 바로 이 팬케이크 정렬에 관한 것입니다.
이 문제에서, $N$개의 팬케이크들의 초기 배치 상태가 주어질 때, 여러분은 이것을 정렬하기 위해 실행해야 할 뒤집기 연산의 최소 횟수를 구해야 합니다.
입력 형식
첫 번째 줄에 테스트 케이스의 수 $T$가 주어집니다. 다음 $T$개 줄에는 테스트 케이스가 주어집니다. 각 테스트 케이스에는 먼저 팬케이크의 수 $N$으로 주어지고, 그 다음 각 팬케이크의 크기를 나타내는 길이가 $N$인 수열이 주어집니다. 맨 밑의 팬케이크 (0번 팬케이크)는 수열에서 가장 먼저 주어집니다.
출력 형식
각 테스트 케이스마다 주어진 팬케이크를 정렬하기 위해 실행해야 할 뒤집기 연산의 최소 횟수를 한 줄에 하나씩 출력합니다.
서브태스크
- (4점) 모든 테스트 케이스는 최대 1번의 뒤집기 연산만으로 정렬할 수 있습니다. 팬케이크들의 크기는 1 이상 $N$ 이하이며 $1 \le T \le 200$입니다.
- (4점) 모든 테스트 케이스는 최대 2번의 뒤집기 연산만으로 정렬할 수 있습니다. 팬케이크들의 크기는 1 이상 $N$ 이하이며 $1 \le T \le 200$입니다.
- (4점) 모든 테스트 케이스는 최대 1번의 뒤집기 연산만으로 정렬할 수 있습니다. 팬케이크들의 크기는 1 이상 1,000,000 이하이며 $1 \le T \le 200$입니다.
- (8점) 뒤집기 연산의 횟수는 제한되어 있지 않으며, 따라서 많을 수도 있습니다. 팬케이크들의 크기는 1 이상 1,000,000 이하이며 $1 \le T \le 200$입니다.
- (5점) 4번과 같지만, $1 \le T \le 6,000$입니다. 테스트 케이스의 수가 많을 수 있으므로, 여러분의 프로그램은 반드시 (매우) 효율적이어야 합니다.
예제 1 (서브태스크 1에 포함)
| 입력 | 출력 |
|---|---|
| 2 4 4 3 2 1 8 8 7 6 5 4 1 2 3 |
0 1 |
첫 번째 테스트 케이스는 이미 정렬되어 있으므로 뒤집을 필요가 없습니다. 두 번째 테스트 케이스는 $flip(5)$만으로 정렬 가능합니다.
예제 2 (서브태스크 2에 포함)
| 입력 | 출력 |
|---|---|
| 3 4 4 3 2 1 8 8 7 6 5 4 1 2 3 5 5 1 2 4 3 |
0 1 2 |
첫 번째와 두 번째 테스트 케이스는 예제 1과 같네요. 세 번째 테스트 케이스는 $flip(3)$과 $flip(1)$ 연산을 차례로 실행하면 정렬할 수 있습니다.
예제 3 (서브태스크 3에 포함)
| 입력 | 출력 |
|---|---|
| 2 5 555555 111111 222222 444444 333333 8 1000000 999999 999998 999997 999996 999995 999994 999993 |
2 0 |
첫 번째 테스트 케이스는 $flip(3)$과 $flip(1)$을 차례대로 실행하면 정렬 가능합니다. 두 번째 입력은 정렬되어 있으므로 뒤집을 필요가 없습니다.
예제 4 (서브태스크 4, 5에 포함)
| 입력 | 출력 |
|---|---|
| 2 5 555555 111111 222222 444444 333333 8 1000000 999999 999998 999997 999996 999995 999994 999993 5 3 8 7 6 10 |
2 0 4 |
첫 번째와 두 번째 테스트 케이스는 예제 3과 같습니다. 세 번째 테스트 케이스 (위에 예제로 나와 있는 것입니다) 아래의 2가지 방법으로 4번의 연산으로 정렬할 수 있습니다.
- 방법 1: $flip(0), flip(1), flip(2), flip(1)$: 4번.
- 방법 2: $flip(1), flip(2), flip(1), flip(0)$: 4번.
4번 이하의 뒤집기로 정렬할 방법이 없으므로, 이것이 최소입니다.