[백준/dp] 2631번 : 줄세우기

- 문제 : https://www.acmicpc.net/problem/2631

 

정답 풀이 

주어진 배열을 오름차순 정렬하기 위해 움직여야하는 최소 원소의 개수를 출력하는 문제

 

다이나믹 프로그래밍으로 주어진 배열에서 len(배열) - len(가장 긴 증가하는 부분수열)를 구하면 된다. 

가장 긴 증가하는 부분 수열의 원소들은 그대로 두고, 속하지 않는 원소들만 움직이면 최소한으로 원소를 움직일 수 있기 때문이다. 

 

풀이 과정

1. dp는 i번째 원소가 속하는 증가하는 부분수열의 최대 길이를 저장한다. 부분 수열에는 원소 개수가 최소 1개는 있으므로 1로 배열을 초기화한다. 

2. 주어진 원소를 순회하면서 arr[i](i번째 원소)와 arr[j] 원소([1, i - 1])에 대해 arr[i] > arr[j]인 경우에 대해 연산을 진행한다. 

    2-1. arr[i]> arr[j] 이므로 arr[i]는 이전의 arr[j]가 포함된 증가하는 부분수열에 포함될 수 있다. 그런데 이때 arr[i]가 다른 부분 수열에 속해있을 수 있으므로 dp[i]와 dp[j] + 1 중 최댓값을 dp[i]에 저장한다. 

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

3. 이렇게 구한 dp의 값 중 최댓값이 가장 긴 부분수열의 길이이므로 이 값을 n에서 뺀다. 

n - max(dp)

 

 

n = int(input())

arr = [0]
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))

 

 

Reference

https://velog.io/@soobin519/Python-%EB%B0%B1%EC%A4%80-2631-%EC%A4%84%EC%84%B8%EC%9A%B0%EA%B8%B0