[AlgorithmSolving][DP] JUNGOL_1871: 줄세우기

1. 문제 내용

• 문제:

  KOI 어린이집에는 N명의 아이들이 있다. 오늘은 소풍을 가는 날이다.  선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다.  선생님은 아이들을 효과적으로 보호하기 위해 목적지까지 번호순서대로 일렬로 서서 걸어가도록 하였다. 

  이동 도중에 보니 아이들의 번호순서가 바뀌었다.  그래서 선생님은 다시 번호 순서대로 줄을 세우기 위해서 아이들의 위치를 옮기려고 한다.  그리고 아이들이 혼란스러워하지 않도록 하기 위해 위치를 옮기는 아이들의 수를 최소로 하려고 한다.

  예를 들어, 7명의 아이들이 다음과 같은 순서대로 줄을 서 있다고 하자.

  3 7 5 2 6 1 4

  아이들을 순서대로 줄을 세우기 위해, 먼저 4번 아이를 7번 아이의 뒤로 옮겨보자. 그러면 다음과 같은 순서가 된다.

  3 7 4 5 2 6 1

  이제, 7번 아이를 맨 뒤로 옮긴다.

  3 4 5 2 6 1 7

  다음 1번 아이를 맨 앞으로 옮긴다.

  1 3 4 5 2 6 7

  마지막으로 2번 아이를 1번 아이의 뒤로 옮기면 번호 순서대로 배치된다.

  1 2 3 4 5 6 7

  위의 방법으로 모두 4명의 아이를 옮겨 번호 순서대로 줄을 세운다.  위의 예에서 3명의 아이만을 옮겨서는 순서대로 배치할 수가 없다.  따라서, 4명을 옮기는 것이 가장 적은 수의 아이를 옮기는 것이다.

  N명의 아이들이 임의의 순서로 줄을 서 있을 때, 번호 순서대로 배치하기 위해 옮겨지는 아이의 최소 수를 구하는 프로그램을 작성하시오.

• 입력:

  입력 파일의 첫째 줄에는 아이들의 수 N이 주어진다. 둘째 줄부터는 1부터 N까지의 숫자가 한 줄에 하나씩 주어진다.  N은 2 이상 200 이하의 정수이다.

• 출력:

  출력 파일의 첫째 줄에는 번호 순서대로 줄을 세우는데 옮겨지는 아이들의 최소 수를 출력한다.

• 예제 입력:

  7
  3
  7
  5
  2
  6
  1
  4
  

• 예제 출력:

  4
  

2. 문제 유형 파악

이 문제는 일렬로 선 아이들의 순서를 맞추기 위해 ‘최소 이동 횟수’를 구하는 문제지만, 그 이면에는 동적계획법 중에서도 LIS(Longest Increasing Subsequence, 가장 긴 증가하는 부분 수열) 알고리즘이 숨어있습니다.

• 발상의 전환:

  ‘어떤 아이들을 움직여야 할까?’에 초점을 맞추면 경우의 수가 너무 많아집니다. 반대로 ‘어떤 아이들을 제자리에 가만히 두어야 할까?’로 관점을 바꿔야 합니다. 아이들을 최소로 움직이려면, 이미 번호 순서대로 잘 서 있어서 움직일 필요가 없는 아이들의 수를 최대로 만들면 됩니다.

• 시간 복잡도 분석:

  입력으로 주어지는 아이들의 수 N은 최대 200입니다. 따라서 이중 반복문을 사용하는 $O(N^2)$ 시간 복잡도의 DP 테이블로 LIS를 구하더라도 연산 횟수는 40,000번에 불과하여 시간 초과 없이 아주 넉넉하게 통과할 수 있습니다.

3. 문제를 풀기 위한 핵심 아이디어

이 문제를 풀기 위한 핵심은 ‘전체 아이들의 수 - LIS의 길 = 최소 이동 횟수’입니다.

1. 이동하지 않는 아이들은 ‘증가하는 부분 수열’을 이룬다

   가만히 서 있는 아이들은 서로 연속해서 붙어있을 필요는 없지만, 그들의 번호는 반드시 오름차순으로 증가하고 있어야 합니다. 문제의 예시인 [3, 7, 5, 2, 6, 1, 4]를 살펴보겠습니다. 이 배열에서 순서가 맞게 증가하는 수열을 찾아보면 [3, 5, 6]을 발견할 수 있습니다. 이 3명의 아이들을 기준점으로 삼아 가만히 두고, 나머지 4명의 아이들(7, 2, 1, 4)만 규칙에 맞게 사이사이나 맨 앞/뒤로 빼서 옮기면 됩니다.

2. 이동을 최소화하려면 기준점(LIS)를 최대화하라

   기준점이 되는 ‘움직이지 않는 아이들’이 많을수록, 내겨 옮겨야 하는 아이들의 수는 줄어듭니다. 즉, 주어진 배열에서 만들 수 있는 ‘가장 긴 증가하는 부분 수열의 길이’를 찾으면, 그것이 곧 ‘움직일 필요가 없는 최대 아이들의 수’가 됩니다.

3. 1차원 DP 테이블의 정의와 점화식

   LIS의 길이를 구하기 위해 다음과 같이 DP 배열을 정의하고 채워나갑니다.

   • DP[i]의 정의:

     i번째 아이를 마지막으로 하는 가장 긴 증가하는 부분 수열의 길이. (초기값은 모두 자기 자신만 포함하므로 1입니다.)

   • 점화식:

     현재 확인 중인 i번째 아이 앞쪽(0부터 i-1까지, 이를 j라 칭함)에 서 있는 아이들을 쭉 훑어봅니다.
     만약 앞쪽 아이의 번호가 현재 아이의 번호보다 작다면(arr[j] < arr[i] ), 증가하는 수열을 이어갈 수 있다는 뜻입니다.
     이때, j번째 아이까지의 LIS 길이에 자신을 붙인 값(DP[j]+1)과 기존에 알고 있던 DP[i] 값 중 더 큰 값으로 갱신합니다.

     • 점화식: if arr[j] < arr[i]: DP[i] = max(DP[i], DP[j] + 1)

   모든 탐색이 끝난 후, DP 배열에 저장된 값 중 최댓값이 바로 LIS의 길이입니다. 최종 정답은 N-max(DP)를 출력하면 됩니다.

4. DP 배열의 초기 값은 모두 1로 초기화

   LIS에서 부분 수열의 최소 길이는 수학적으로 무조건 1입니다. 앞에 있는 어떤 숫자들과도 이어지지 못하더라도, 최소한 자기 자신 하나만 덩그러니 서 있는 수열은 언제나 성립하기 때문입니다.

4. 코드

이 문제의 코드는 다음과 같습니다.

import sys

def solve():
    input = sys.stdin.readline

    n = int(input())

    num_list = [int(input()) for _ in range(n)]

    dp = [1] * n

    for i in range(n):
        for j in range(0, i):
            if num_list[i] > num_list[j]:
                dp[i] = max(dp[i], dp[j]+1)

    print(n - max(dp))

solve()