https://www.acmicpc.net/problem/18353
LIS (가장 긴 증가하는 부분순열) 문제이다.
LIS 에 핵심적인 점화식 개념을 써놓았다.
n = int(input()) a = list(map(int,input().split())) d = [1] * n for i in range(n): for j in range(i): if a[j] > a[i]: d[i] = max(d[j] + 1, d[i]) print(n - max(d))
Last updated 3 years ago