H. Sleepy Cow Sorting

Editor: 김정현(powergee)

문제 상황 설명

정렬되지 않은 소들을 번호에 대하여 오름차순이 되도록 정렬해야 합니다. 그런데 여기서 소를 이동시킬 때 가장 앞에 있는 소를 몇 칸 뒤로 이동시키는 것만 가능합니다. 이러한 상황에서 소들을 완전히 정렬시키려면 최소한 소를 몇 번 이동시켜야 할까요?

문제 풀이

가장 앞의 소를 뒤로 옮기는 연산만으로 소의 배열을 정렬시키려면 어떻게 해야 할까요? 이를 알아보기 위해 예제 입력을 분석해 보겠습니다.

4
1 2 4 3

이 상황에서 최소 3번 가장 앞에 있는 소를 이동시켜야 합니다. 그 세 번의 연산은 아래와 같습니다.

1. 1번 소를 2칸 뒤(4번 뒤)로 이동시킵니다. 이때 배열은 "2413"입니다.

2. 2번 소를 2칸 뒤(4번 뒤)로 이동시킵니다. 이때 배열은 "4123"입니다.

3. 4번 소를 3칸 뒤(3번 뒤)로 이동시킵니다. 이때 배열은 "1234"입니다. 배열의 정렬이 완료되었습니다.

위 과정을 분석해보면 문제의 풀이법을 알 수 있습니다. 위 풀이에서 배열은 "1243", "2413", "4123", "1234" 순으로 변화하는데, 이 네가지 수열은 아래 표와 같이 분할하여 생각 할 수 있습니다.

구분	소의 이동	전체 수열	수열의 앞 (정렬되지 않은 부분)	수열의 뒤 (정렬된 부분)
이동 전	-	"1243"	"124"	"3"
1회	1번 소를 2칸 뒤로	"2413"	"24"	"13"
2회	2번 소를 2칸 뒤로	"4123"	"4"	"123"
3회	4번 소를 3칸 뒤로	"1234"	-	"1234"

즉, 가장 앞의 소를 뒤로 옮기면서 정렬하는 것은 곧 가장 앞의 소를 뒤쪽 수열에 정렬된 순서로 삽입하면서 정렬하는 것이 됩니다. 따라서 어떤 수열 $s$가 주어졌을 때, 이 수열의 뒤에 옳게 정렬된 부분 수열이 $s_2$라면 소를 이동시키는 연산은 최소 $\textrm{length}(s)-\textrm{length}(s_2)$번 수행되어야 합니다. 왜냐하면 수열의 정렬되지 않은 앞부분 (길이가$\textrm{length}(s)-\textrm{length}(s_2)$인 부분)을 하나씩 정렬된 부분에 삽입하며 정렬하기 때문입니다.

이를 토대로 예제를 해석하면 "1243"에서 정렬된 뒷 부분은 "3"뿐이고, 이것의 길이가 1, 전체 길이가 4이므로, 4-1=3, 정답은 3이 됩니다.

다른 예제를 들어 만약 입력이 "753214689"라면, 여기서 정렬이 된 뒷부분은 "14689"입니다. 이것의 길이가 5, 전체 길이가 9이므로 같은 방법으로 정답은 4가 됩니다.

정답 소스 (C++)

#include <iostream>
#include <vector>

int main()
{
    int n;
    scanf("%d", &n);
    std::vector<int> vec(n);

    for (int i = 0; i < n; ++i)
        scanf("%d", &vec[i]);

    int rightLen = 1;
    for (int i = n - 1; i > 0; --i)
    {
        if (vec[i - 1] < vec[i])
            ++rightLen;
        else break;
    }

    printf("%d", n - rightLen);

    return 0;
}