2631. 줄세우기 (Python)

2631번: 줄세우기

풀이

 LIS(Longest Increasing Subsequence, 최장 증가 부분 수열)을 활용하여 해결할 수 있는 문제이다. 입력으로 주어진 아이들 중에서 LIS의 길이를 찾은 후 이에 해당하지 않는 나머지 아이들을 옮기면 위치를 옮기는 아이들의 수를 최소로 할 수 있다.

 

 예제를 보면 다음과 같다. 

 해당 리스트에서 LIS는 {3, 5, 6}에 해당하고 길이는 3이다. 이 3명을 제외한 나머지 7, 2, 1, 4번의 아이들을 옮기면 최소한의 이동으로 번호 순서대로 줄을 세울 수 있다.

 

코드

if __name__ == '__main__':
    N = int(input()) # 아이들의 수
    children = [] # 아이들 리스트

    for i in range(N):
        children.append(int(input()))

    # LIS 길이를 담기 위한 dp 리스트
    # dp[n]은 0부터 n번째 인덱스까지 봤을 때 증가 부분수열 중 가장 긴 길이를 의미한다.
    dp = [1] * N

    for i in range(N):
        for j in range(i):
            if children[i] > children[j]:
                dp[i] = max(dp[i], dp[j] + 1)

    # LIS의 길이에 해당하지 않는 나머지 아이들을 옮기면 번호 순서대로 줄을 세울 수 있다.
    print(N - max(dp))