[백준] 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)
글 쓰다가 기억났다. 행복하다🥰
Author And Source
이 문제에 관하여([백준] 2565번: 전깃줄), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@kyy00n/백준-2565번-전깃줄저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)