줄세우기

첫 제출에 바로 정답이었던 비교적 쉽게 풀었던 문제를 가져왔다. 최근 백준 문제 별로 테스트 케이스를 추가할 수 있는 사이트를 만들고 있는데, 거기에 집중하다가 새벽 2시가 다 되어 부랴부랴 포스팅 하는 중이다.

줄세우기 문제는 N명의 아이들이 있을 때, 번호 순서대로 아이들을 줄세우기 위해 옮겨야 하는 아이들의 최소 수를 구하는 문제이다.

입력 예제를 살펴보면 3 7 5 2 6 1 4 순으로 아이들이 서있다고 한다.

  • 3 7 4 5 2 6 1 [4번을 7번 뒤로 옮긴다.]
  • 3 4 5 2 6 1 7 [7번을 맨 뒤로 옮긴다.]
  • 1 3 4 5 2 6 7 [1번을 맨 앞으로 옮긴다.]
  • 1 2 3 4 5 6 7 [2번을 1번 뒤로 옮긴다.]

이렇게 최소 4명의 아이들을 옮겨야 해서 답은 4이다.

여기서 주목해야 할 점은 옮겨진 아이들 1번, 2번, 4번, 7번을 제외하고 ‘3 5 6’이 ‘3 7 5 2 6 1 4’ 수열의 최대 증가 순열이라는 점이다.

최대 증가 순열을 찾으면 이 순열을 이루는 숫자들을 기준으로, 나머지 숫자들을 배치해주면 숫자들을 최소로 옮길 수 있게 된다!

따라서, 저번 포스팅에서 다루었던 DP문제 Longest Increasing Subsequence를 활용하면 쉽게 풀 수 있다.

아이들의 번호가 주어졌을 때, 가장 긴 증가하는 부분 순열을 찾고 아이들의 수에서 순열의 길이를 빼면 최소로 옮겨야 하는 아이의 수가 나온다.

코드에 대해서는 Longest Increasing Subsequence 여기서 다루었기 때문에 이번 포스팅에서는 자세히 설명하지 않아도 될 것 같다.


CODE

import sys
n=int(input())
numbs=list(int(sys.stdin.readline()) for _ in range(n))

dp=list(0 for _ in range(n+1))

for i in range(n):
    for j in range(i):
        if numbs[i]>numbs[j]:
            if dp[i]<=dp[j]:
                dp[i]=dp[j]+1

    if dp[i]==0:
        dp[i]=1

print(n-max(dp))


DP 대표 유형

[다시 풀어보기]