[BOJ 2759] 팬케익 뒤집기

문제

2759번: 팬케익 뒤집기

---

꽤 재미있는 문제였다.

 

문제에서 명시해둔 최대로 뒤집을 수 있는 횟수인 $2n-3$이 핵심이다.

팬케익의 숫자는 $1$부터 $n$까지 있다. 당연하게도, 정렬되어있을때, 크기 $i$인 팬케익은 $i$번째 위치에 있을 것이다.

크기 $i$인 팬케익을 $i$번째 위치로 보내는 가장 나이브한 풀이를 생각해보자. 

1. 크기 $i$인 팬케익의 위치를 $p$라고 하자.
2. $p$위치에서 팬케익을 뒤집는다. 이때 크기 $i$인 팬케익은 첫번째 위치로 갈 것이다.
3. 그리고 $i$에서 다시 팬케익을 뒤집는다.
4. 그러면 크기 $i$인 팬케익이 $i$번째 위치로 옮겨진다.
5. 이를 크기 $n$인 팬케익부터 크기 $1$의 팬케익까지 차례대로 반복한다.

위의 풀이를 이용하면 $2n-3$번 이내로 팬케익을 뒤집어서 정렬할 수 있다. 그 증명은 아래와 같다.

• $i == 2$ 인 경우, 펜케익이 첫번째 위치에 있다면 한번만 뒤집으면 위치로 보낼 수 있고, 두번째 위치에 있다면 뒤집을 필요가 없다. ($-1$ ~ $-2$)
• $i == 2$까지 모두 뒤집은 경우, 맨 마지막 숫자인 $i == 1$은 첫번째 위치밖에 갈 수 없기 때문에, 뒤집을 필요가 없다. ($-2$)
• $i > 2$ 인 경우에는 항상 2번 뒤집어야한다.

따라서 최대 $2 \times (n-2) + 1 = 2n-3$번 뒤집어서 정렬할 수 있다.