알고리즘/dp

[백준]2631 줄세우기 #LIS#dp

씩씩한 IT블로그 2020. 6. 15. 17:05
반응형

최소로 움직이는 횟수 = 전체명수 - 처음에 최대로 정렬되어있는 개수(LIS)

LIS를 구성하는 요소를 제외하고는 모든 유치원생이 각자 한번씩은 반드시 움직여야 한다.

N=int(input())
L=[]
for i in range(N):
    L.append(int(input()))

lis=[1 for i in range(N)]

for i in range(1,N):
    for j in range(0,i):
        if L[j]<L[i] and lis[i]<lis[j]+1:
            lis[i]=lis[j]+1
print(N-max(lis))
반응형