[백준 BOJ_2565] 전깃줄 Python 풀이

출처: 백준 온라인 저지

문제

풀이

이 문제는 가장 긴 증가하는 부분 수열 (Longest Increasing Subsequence)의 응용 문제 입니다.

우선, 각 전깃줄을 tuple로 받은 뒤 list에 넣어줍니다.

그런 뒤 list를 tuple 첫 번째 값에 따라 오름차순으로 정렬해줍니다. 그렇게 되면 첫 번째 값은 증가하고 있으니 두 번째 값에서 증가하지 않는 부분이랑 연결된 전깃줄을 없애야 최솟값이 됩니다. 그럼 두 번째 값의 가장 긴 증가하는 부분 수열의 길이를 구해 전깃줄의 총 개수에서 빼주면 최솟값이 나옵니다.

코드

N = int(input())
A = [tuple(map(int, input().split())) for _ in range(N)]
A.sort(key= lambda a: a[0])
cache = [1 for _ in range(N)]
for i in range(N):
    for j in range(i):
        if A[i][1] > A[j][1] and cache[i] <= cache[j]:
            cache[i] = cache[j] + 1
print(N-max(cache))