[BOJ/백준] 2631 줄세우기

# 2631 줄 세우기
# LIS의 길이를 구하기 위한 방법 복잡도 O(Nlogn)로 구하기 
N = int(input())
arr = list(int(input()) for _ in range(N))
LIS = []
LIS.append(arr[0])
temp = 0
for number in arr[1:]:
    for ind,val in enumerate(LIS):
        if number > val and number not in LIS:
            temp = number
        elif number < val and number not in LIS:
            LIS[ind] = number
            temp = 0
    if temp:
        LIS.append(temp)
    temp = 0
print(N-len(LIS))
    

 

 

 이 문제는 최장 증가 부분 순열을 활용한 문제이다.  크기대로 줄을 세우는 것이기 때문에, 주어진 배열에서, 가장 긴 증가 부분 순열을 제외하고 나머지 부분을 움직이면 정답을 구할 수 있따.