[백준] 7570번: 줄세우기 Python - Greedy/DP

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

7570번: 줄 세우기

가장 긴 증가하는 수열의 길이를 찾은 후 전체 길이 n에서 빼준다. 

 

n = int(input())
data = list(map(int, input().split())) 

count = 1 # 길이가 1 인 수열로 취급 
max_len = 0 

position = [0] * (n+1)
for i in range(1, len(data)):
    position[data[i]] = i # index를 저장한다. I#NDEX를 1 ~ 로 시작하는걸로 맞춰준다. 

for i in range(1, len(data)-1):
    
    if position[i] < position[i+1]:  # 올바른 순서 , 즉 크기가 증가하는 수열인 경우
        count += 1
        max_len = max(count, max_len)
    else:
        count = 1

print(n - max_len)

 

DP 풀이 

import sys 
input = sys.stdin.readline 
n = int(input())
data = list(map(int, input().split()))
dp = [0]*(n+1)

max_length = 0 
for i in range(n):
    index = data[i] # position 에 해당 지금 숫자가 dp에 저장될 위치임 
    dp[index] = dp[index-1] +1 
max_length = max(dp)
print(n - max_length)