[ 백준 2631 ] 줄세우기 - Python

문제 보기

 

이 문제는 DP 문제이다.

 

N명의 아이들을 번호 순서대로 옮기는 최소한의 수를 구하면 된다. 최소한의 수를 구하기 위해서는 움직이지 않아도 되는 아이들을 구하면 된다. 움직이지 않아도 되는 아이들은 현재 번호 순서에서 가장 긴 증가하는 수열에 해당한다. 

 

알고리즘 과정은 아래와 같다.

1. 가장 긴 증가하는 수열을 구한다.

2. 전체 인원수에서 가장 긴 증가하는 수열의 길이를 뺀다.

 

코드

if __name__ == "__main__":
    N = int(input())  # 아이들의 수
    people = [int(input()) for _ in range(N)]  # 아이들 번호 순서 정보

    # 2차원 dp
    dp = [[0] * N for _ in range(N)]

	# 가장 긴 증가하는 부분수열
    for i in range(N):
        dp[i][i] = 1  # i를 시작점으로 설정.
        for j in range(i + 1, N):
            for k in range(j):
                if people[k] < people[j]:
                    dp[i][j] = max(dp[i][j], dp[i][k] + 1)

    # 가장 긴 증가하는 수열 길이 계산
    lis = 0
    for i in range(N):
        lis = max(lis, max(dp[i]))

    # 전체 길이 - 가장 긴 증가하는 부분수열
    answer = N - lis
    print(answer)