[백준] 2631번: 줄세우기 (Python) | 가장 긴 증가하는 부분 수열 구하기

 

https://www.acmicpc.net/problem/2631

2631번: 줄세우기

 

문제의 핵심은 옮기는 학생의 최소 수를 구하는 것이고, 옮기는 학생의 최소 수는

전체 배열의 길이 - 가장 긴 증가하는 수열의 길이 

와 같다. 

가장 긴 증가하는 수열의 길이는 dp 를 이용하여 구할 수 있다. 우선 dp 의 값을 1로 초기화 한다. 그 이유는 '자기 자신' 만 포함하는 길이가 1 인 수열부터 시작하게 되기 때문이다. 

dp = [1] * (N+1)

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

첫번째 for 문에서 처음부터 마지막 인덱스를 기준으로 검사한다. 

두번째 포문에서 자기자신(arr[i])보다 앞에 있는 숫자들을 검사한다. arr[i] 값 보다 arr[j] 값이 작다면, 증가하는 수열일 가능성이 있다. 

그런데 이 arr[j] 를 포함시킬지 말지 결정이 필요하다. 따라서 dp[i] 값을 갱신할 때는 기존 값과 현재 arr[j] 를 선택했을 때 값을 비교하게 된다.  

dp[i] = max(dp[i], dp[j] + 1)

 

전체 코드 

# https://www.acmicpc.net/problem/2631

answer = int(1e9)

N = int(input())
arr = [0] # index 맞춰주기
for _ in range(N):
    arr.append(int(input()))

dp = [1] * (N+1)

for i in range(1, N+1):
    for j in range(1, i):
        if arr[i] > arr[j]:
            dp[i] = max(dp[i], dp[j] + 1)
# 전체 - 가장 긴 증가하는 수열의 길이
print(N - max(dp))