그건 잘 모르겠지만.

5 2 4 3 1을

1 2 3 4 5로 변경시킨다는 거 아닌가요?

이건 좀 쉬우니까 다른 예제 들어봅시다.

7 

1 4 2 3 7 5 6

이건 어떻게 해야 할까요? 이건

1

4

2

3

7

5

6

이렇게 배치가 되어 있는 것과 같습니다. 이 경우. 사실상 움직일 필요가 없는 건 7 뿐입니다. 왜일까요?

우리는 이걸

1 2 3 4 5 6 7로 바꾸어야 하는데요.

분명한 건. 어떠한 것을 집어서 위로 옮기는 건 이전 위치 > 현재 위치란 것이거든요. 그 순간에.

그러면 잘 생각해 보세요. 6이란 친구는 7보단 밑에 있었어요. 그걸 위로 올려야 하네요.

5라는 친구는 6보다는 위에 있지만 7보단 밑에 있어요. 즉, 위로 올려야 한단 말이지요.

이렇게 시뮬레이션을 시켜 보면..

8 

6 8 1 2 3 4 5 7

이 답이 왜 7이고

8 

1 4 6 7 8 2 3 5 

이 답이 무엇인지도 아실 듯 싶네요. 3시 수업이라.. 수업 중에 증명하거나 할게요.

8
6 1 2 3 4 5 7 8

마찬가지 이유로, 이 친구는 답이 5입니다. 8-3 = 5이기 때문입니다.

일반화 해서 확장시켜 본다면

f[x] = 입력 받은 배열에서의 x의 위치라고 한다면 (단 1<=x<=n)

f[u]<f[u+1]<...<f[n]이 성립하면 u부터 n까지는 이동할 필요가 없습니다.

이것을 증명하긴 그렇고.. 간단하게 시뮬레이션으로 일반화 시켜 봅시다.

일단 어떠한 배열에서 [u,...,n]을 요런 식으로 찾을 수 있다고 해 봅시다.

그렇다면

.. u .. u+1 .... n-1 .. n ..

이런 식으로 배열에 있을 겁니다. 일단 이러한 경우에는..

u부터 n까지는 순서에 잘 맞게 배치되어 있습니다.

이 상태에서, 이러한 질문을 생각해 봅시다. 만약에 f[u] < f[u-1]이면 어떨까요?

만약에 u-1을 올리지 않으면 어떻게 될까요? 이 경우

f[u] < f[u-1]이기 때문에

u 뒤에 u-1이 있게 되고, 이러한 경우 오름차순으로 정렬되지 않을 겁니다. 맞나요? 그렇기 때문에,

책 하나를 뺀 다음, 가장 위에 놓는 연산을 수행해야 합니다.

그러면 어떻게 될까요?

u-1 ... u .. u+1 .... n-1 ... n ... 이 되지 않을까요?

그런데 이 ... 안에 있는 수들은 u-1보다는 작기 때문에, u, u+1, ... , n보다는 작다는 게 자명합니다.

따라서 ...에 있는 수들 역시 가장 위에 놓는 연산을 수행해야 하고 (u-2부터 1까지 차례대로)

(사실 이거 역시 차례대로 시뮬 돌려보면 알 수 있습니다.)

우리는 1부터 u-1까지에 대해서 연산을 수행했으므로, 답은 u-1이 됩니다.

그러면 이분탐색의 판단 함수를 세울 수 있고. 이분탐색 적용 가능하겠지요..??

저의 허접한 질문에 이렇게 장문으로 자세히 설명해주셔서 너무 감사합니다. ㅠㅠ

처음에는 3~4번씩 읽어도 이해하기 어려웠습니다만 시간적 여유를 두고 refresh한 후에 다시 읽어보니 이해가 확 되더군요 !!

덕분에 쉽게 풀고 넘어갈 문제를 깊게 생각하게 만들어주신것같아 감사합니다~! 

한번에 맞췄어요 ㅎㅎ 

윗 분이 좀 어렵게 설명하신 것 같아서 직관적인(?) 힌트를 드리자면 다음과 같습니다.

5

2 4 1 3 5

이런 테스트 케이스에서 움직이지 않아도 될 책은 4, 5 입니다.

5

2 [4] 1 3 [5]

왜냐하면 4, 5를 제외한 다른 책을 적절하게 움직이면 알아서 정렬되기 때문이죠!

순서대로 3을 움직이고, 2를 움직이고, 1을 움직이면 됩니다.

중요한 것은 3, 2, 1 전부 움직여야 하며, 움직일 필요가 없는 책은 하나도 없다는 것입니다. 예를 들어 1과 3만 움직이고 2는 움직이지 않는다면 안 된다는 것입니다.

반드시 전부 움직여야 정렬됩니다. (Why?)

7

5 3 2 6 1 7 4

이 경우도 마찬가지입니다.

움직이지 않아도 될 책은 5, 6,7 입니다.

7

[5] 3 2 [6] 1 [7] 4

왜냐하면 5, 6, 7 을 제외한 다른 책을 움직이면 알아서 정렬되기 때문입니다.

순서대로 4를 움직이고, 3을 움직이고, 2를 움직이고, 1을 움직이면 됩니다.

이 경우도 마찬가지로 4, 3, 2, 1 전부 모조리 움직여야 합니다.(Why?)

조금만 생각해보면 직관적으로 왜 그런지 알 수 있을 것이고 증명도 가능할 것입니다 :)

(저는 이분탐색으로 구현하지 않았습니다.)