LIS, DP - 2631번: 줄세우기

순서대로 배치하기 위해 옮겨지는 아이의 최소 수를 구하는 문제

-> 아이들 중 순서를 바꾸지 않고 그대로 둘 수 있는 최대 집합의 길이 구하기
-> 최장 증가 부분 수열(LIS) 구해서
n - len(lis) 가 옮겨지는 아이의 최소 수가 됨!

n = int(input())
nums = []
for _ in range(n):
    num = int(input())
    nums.append(num)

lis = [nums[0]]

for i in range(1, n):
    # lis의 가장 마지막 원소(가장 큰 숫자)보다 크다면 맨 끝에 추가
    if nums[i] > lis[-1]:
        lis.append(nums[i])
    # 작다면 lis 내부 원소와 교환
    else:
        # lis를 맨 앞부터 보면서 첫번째로 nums[i]보다 큰 원소를 찾았다면 해당 원소를 nums[i]로 대체하기 -> 이후에 더 많은 숫자가 뒤에 올 수 있게 됨 (최장 증가 부분 수열을 찾을 수 있음)
        for j in range(len(lis)):
            if lis[j] > nums[i]:
                lis[j] = nums[i]
                break
# 최소 교환 횟수 = 전체 아이들 수 - lis길이 (증가하는 부분 수열에 해당하는 아이들은 가만히 두고 그 외 아이들만 교환하면 되므로)
print(n - len(lis))