대한 어린이집에 올해 입학한 어린이들이 놀이터에 한 줄로 서있다. 모든 어린이들에게는 입학할 때 주어진 번호가 있고 모두 옷에 번호표를 달고 있다. 그런데 어린이들은 아직 번호 순서대로 줄을 잘 서지 못하므로 선생님이 다음과 같은 방법을 사용해서 번호순서대로 줄을 세우려고 한다.
방법: 줄 서있는 어린이 중 한 명을 선택하여 제일 앞이나 제일 뒤로 보낸다.
위의 방법을 사용할 때 어린이가 이동해서 빈자리가 생기는 경우에는 빈자리의 뒤에 있는 어린이들이 한 걸음씩 앞으로 걸어와서 빈자리를 메꾼다.
예를 들어, 5명의 어린이들에게 1부터 5까지의 번호가 주어져 있고, 다음과 같은 순서로 줄 서있다고 하자.
5 2 4 1 3
위 방법을 이용해서 다음과 같이 번호순서대로 줄을 세울 수 있다.
1번 어린이를 제일 앞으로 보낸다. (5 2 4 1 3 → 1 5 2 4 3)
4번 어린이를 제일 뒤로 보낸다. (1 5 2 4 3 → 1 5 2 3 4)
5번 어린이를 제일 뒤로 보낸다. (1 5 2 3 4 → 1 2 3 4 5)
위의 예에서는 세 명의 어린이를 제일 앞이나 제일 뒤로 보내 번호순서대로 줄을 세웠다. 그리고 두 명 이하의 어린이를 제일 앞이나 제일 뒤로 보내는 방법으로는 번호순서대로 줄을 세울 수 없다. 그러므로 이 경우에는 최소한 세 명의 어린이를 이동하여야 번호순서대로 줄을 세울 수 있다.이 문제는 처음에 줄서있는 상태에서 위 방법을 이용해서 번호순서대로 줄을 세울 때 앞이나 뒤로 보내는 어린이 수의 최솟값을 찾는 것이다.
풀이
풀이가 맞는지 아닌지 증명하는게 까다로웠던 문제이다.
처음에는 단순한 그리디 접근으로 생각했다.
조건을 걸어 앞/뒤로 보내는 경우를 생각하여 특정원소와 그 원소보다 작거나, 큰 원소의 위치를 조건으로 하여 접근했지만 15432에서 3, 4, 5를 뒤로 보내는 조건과 23451에서 1을 앞으로 보내는 조건과 같이 각각의 원소마다 체크해야하는 조건이 너무 많아지므로 다시 생각하게 되었다.
결론은 LIS의 응용이었다.
LIS는 Longest Increasing Subsequence로, 가장 긴 증가하는 부분수열을 의미한다. LIS중에서 이 문제는 Continious한 경우만 체크해주어야 한다. 연속된 정수를 결국 오름차순 정렬해야하는 경우이고, 중간에 insert하는 것이 아닌 앞/뒤로 이동시켜 정렬을 해야하기 때문에 결국 이미 연속하여 부분적으로 정렬이 되어있지 않는 경우는 필요없기 때문이다.
위의 예제를 예시로 들면 5 2 4 1 3인 경우에, 가장 긴 연속적으로 증가하는 부분수열은 2, 3이다. 이를 제외하고는 전부 앞/뒤로 옮기는 과정을 통해 정렬을 해야 하므로, 결국 전체길이 - 가장 긴 연속적으로 증가하는 부분수열 의 길이 가 이 문제의 해가 된다.
