[Baekjoon]백준 2565 전깃줄(골드 5) - Python

문제설명 1

문제설명 2

문제를 살펴보면 가장 긴 증가하는 부분 수열의 응용 문제임을 확인할 수 있다

연결되는 위치를 A를 기준으로 정렬한 후에, 그 중에서 가장 긴 부분 수열의 길이를 찾고, 이를 입력받은 수에서 빼면 된다

그 수가 없애야 하는 전깃줄의 최소 개수가 되기 때문이다

 

그래서 리스트를 만들어 각 줄마다 연결된 번호 위치를 저장해주었고, 각 index의 최대 길이를 찾기 위한 리스트를 만든다

이후 첫번째 for문은 LIS 확인을 위해, 두번째 for문은 조건을 만족한 경우 최대 길이를 저장하는 리스트를 업데이트해준다

최종적으로 리스트의 최댓값이 겹치지 않는 경우의 최대 전깃줄의 개수이다

따라서 정답은 처음 입력받은 전깃줄의 개수에서 뺀 값이 없애야 하는 전깃줄의 최소 개수임을 알 수 있다

num = int(input())
point = []

for _ in range(num):
    point.append(list(map(int, input().split())))
    
point = sorted(point, key = lambda x : x[0])
result = [1] * num

for i in range(num):
    for j in range(i):
        if point[j][1] < point[i][1]:
            result[i] = max(result[i], result[j] + 1)

print(num - max(result))