[백준 - Python] 2565. 전깃줄

https://www.acmicpc.net/problem/2565

2565번: 전깃줄

 

코드

N = int(input())

dp = [1] * N

lines = sorted([list(map(int, input().split())) for _ in range(N)], key = lambda x : x[0])

for i in range(N):
    for j in range(i):
        if lines[i][1] > lines[j][1]:
            dp[i] = max(dp[i], dp[j] + 1)

print(N - max(dp))

 

대표적인 LIS(Longest Increasing Subsequence) 최장 증가 부분 수열 알고리즘 문제로 볼 수 있다.

해당 알고리즘은 DP를 활용해서 구현할 수 있다.

 

1로 초기화 된 DP 리스트를 선언해준다.

해당 dp[i]에는 i번째 선의 위치까지 최대 몇 개의 전깃줄이 얽히지 않는지를 저장해 준다.

 

전봇대 A와의 연결 위치를 기준으로 오름차순 정렬을 해주었다.

 

각 전깃줄을 돌면서, 현재 돌고 있는 전깃줄보다 시작점이 작은 전깃줄들을 확인하면서

끝 점이 현재 돌고 있는 전깃줄의 끝 점보다 작은 경우에

즉, 전깃줄이 교차하지 않는 경우에 dp[j]의 카운팅을 1 늘려준 값과 현재 위치의 dp[i] 값 중 최댓값으로

dp[i]를 갱신해준다.

 

잘라야 하는 전깃줄의 최소 개수를 구해야 함으로

전체 전깃줄 갯수에서 dp리스트의 최댓값을 빼주면 답이 된다.