[Python/파이썬] 백준 2631번 줄세우기

요구사항 정리

아이들의 이동을 최소로 하여 아이들의 번호가 오름차순으로 정렬되도록 만들자.
예를 들자면, 3 7 5 2 6 1 4와 같이 아이들이 일렬로 서있다고 할 때, 이것을 최소한의 이동만으로 1 2 3 4 5 6 7로 만들어주면 된다.

입력

첫째줄 : 아이들의 수 N (2 ≤ N ≤ 200, N은 정수)
둘째줄~ : 1~N까지의 숫자가 한 줄에 하나씩 주어짐

출력

아이들을 번호 오름차순으로 정렬하기 위해 최소한으로 옮기는 횟수 출력.

코드

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

# LIS
dp = [1]*n
for i in range(n):
    for j in range(i):
        if arr[i] > arr[j]:
            dp[i] = max(dp[i], dp[j]+1)

print(n-max(dp))

 

방법만 알면 쉬운데, 방법을 아는게 어려운 문제였다

 

어지럽혀진 정렬을 최소한의 이동만으로 올바르게 정렬하려면 제 위치에 있지 않은 숫자들을 찾아내고, 그 숫자들이 알맞는 위치를 찾아가게 도와주면 된다. 이렇게 하기 위해서는 누가 제 위치에 있는지, 누가 제 위치에 있지 않은지 알아내는 것이 필요하다. 

 

그렇다면 맞는 위치에 있는 숫자들은 누구일까? 예를 들어 3 7 5 2 6 1 4가 있다고 하면 이 중 알맞은 위치에 있는 사람은 누구일지 생각해보자.

 

3 7 5 2 6 1 4

 

빨간색으로 칠한 세 숫자를 보면 오름차순으로 정렬이 되어 있는 것을 볼 수 있다. 바로 이 숫자들이 알맞는 위치에 있는 것이다. 그리고 이건 알고리즘 공부를 좀 한 사람이라면 무엇인지 알 수 있을 것이다.

 

최장 증가 부분 수열(LIS, Longest Increasing Subsequence). 바로 수열의 부분수열 중 가장 길게 증가하는 부분 수열을 말하는 것인데, 딱 이 문제가 찾는 부분 수열이다. 그렇기에 우리는 최장 증가 부분 수열의 길이를 구하여 이 값을 N에서 빼면 구하려던 답이 나오게 된다.

 

최장 증가 부분 수열에 대한 자세한 설명은 여기로.