[백준] 2565번: 전깃줄

문제보기

나 왜 이거 기억 안 나지? LIS 계산하는 방법이 기억이 안나서 저번에 풀었던 걸 보고 풀었다😭 속상

처음에 A를 기준으로 입력된 전깃줄들을 정렬해주고

B의 숫자를 전체 수열로 하는 가장 긴 증가하는 부분수열의 길이를 전체 전깃줄 개수에서 빼면 답이 나온다. 그건 알겠는데 왜 dp를 저렇게 계산하지?

N = int(input())
l = [list(map(int, input().split())) for _ in range(N)]
l.sort(key=lambda e: e[0])
seq = [a[1] for a in l]
dp = [1 for _ in range(N)]
for i in range(N):
    maxLen = -1
    idx = -1
    for j in range(i):
    	# seq[i] 이전에 seq[i] 보다 작은 모든 seq[j]에 대해 수행하기 위해서.. 흑흑
        if seq[j] < seq[i] and maxLen < dp[j]:
            maxLen = dp[j]
            idx = j
        if idx != -1:
            dp[i] = dp[idx] + 1
ans = N - max(dp)
print(ans)

글 쓰다가 기억났다. 행복하다🥰