[백준]2565번 전깃줄 - DP

 

n = int(input())

line = [[0] * 2 for i in range(n)]

for i in range(n):
    line[i][0], line[i][1] = map(int, input().split())

line.sort(key=lambda x: x[0])
length = [0] * n
for i in range(n):
    length[i] = 1
    for j in range(i):
        if line[j][1] < line[i][1]:
            length[i] = max(length[i], length[j] + 1)

print(n-max(length))

 

코드 설명

먼저 전깃줄의 이어진 정보를 line 이차원 리스트에 저장한다.

그 후 한쪽의 전봇대를 기준으로 번호를 정렬하여 준다. n 번의 반복문을 진행하고 length(dp)리스트의 값을 1로 정한다.

만약 B 전봇대에서 i 번째의 번호가 j 보다 크다면 i에 저장된 값과 j+1 의 값중 큰 것으로 업데이트 하여 준다.

전깃줄의 수에서 최댓값을 뺌으로써 정답을 구할 수 있다.

 

Point : LIS 알고리즘을 이용하여 문제를 풀 수 있다.

A 전봇대를 번호순으로 먼저 정렬해주는 작업이 필요하다. 그 후에 B 전봇대에서 각 번호별 LIS(가장 긴 증가하는 부분 수열)값을 구해주면 된다. 

교차하지 않게 하기 위해 없애야 하는 전깃줄의 최소 개수는 -> 전체 수 - 최대로 연결 할 수 있는 전깃줄의 수와 동일한 맥락이다.