[백준 BOJ / Python] 2565번 전깃줄 DP

문제

두 전봇대 A와 B 사이에 몇 개의 전깃줄을 제거해야 교차하는 전깃줄이 없는지 구하는 문제이다. 즉, 최소한의 제거할 수 있는 전깃줄의 개수를 도출해야 한다.

< 그림 1 >

풀이

• 서로 전깃줄이 교차하지 않게 하기 위해 없애야 하는 전깃줄의 최소 개수를 구해야 한다.
• 예를 들어, A-1번과 B-8번이 연결된 전깃줄보다 A-3번과 B-9번이 연결된 전깃줄이 더 아래 있는 것을 알 수 있다.
• 이를 통해 A의 번호가 순차적으로 커질 때, 각각의 A와 연결된 B의 번호도 더 커진다면 교차하지 않는 전깃줄의 개수를 구할 수 있음을 알 수 있다.
• A의 정렬된 번호를 리스트의 인덱스로 두고, B의 번호를 가지고 가장 긴 증가하는 수열(LIS)을 구함으로써 교차하지 않는 전깃줄의 최대 개수(c)를 구할 수 있다.

[Study/Algorithm] - [알고리즘 / Python] 가장 긴 증가하는 부분 수열 (LIS)

[알고리즘 / Python] 가장 긴 증가하는 부분 수열 (LIS)

알고리즘

1. A 전봇대의 번호를 기준으로 정렬한다.
2. B 전봇대의 번호를 기준으로 LIS (DP 활용)를 수행한다.
3. dp에 담긴 숫자 중 가장 큰 숫자(c)를 구한다.
4. 전체 전깃줄 개수에서 c를 빼주어 최소한 제거해야 하는 전깃줄의 개수를 구한다.

Python 코드

import sys
input = sys.stdin.readline
n = int(input())
wire = [tuple(map(int,input().split())) for _ in range(n)]
wire.sort() # A 전봇대 기준으로 정렬 필수

# 1로 초기화 => 자기 자신의 원소를 의미하는 1
dp = [1]*n

# LIS
for i in range(1,n): # A 전봇대의 번호 i
    for j in range(i): # A 전봇대의 번호 j (i보다 이전에 있는 번호들)
    	# 만약 나중 번호인 i의 B 전봇대 연결 번호가 이전 번호인 j의 B 전봇대 연결 번호보다 크면,
        # 현재 A 전봇대의 i 번째까지의 번호들과 교차 없이 연결 가능한 전깃줄 개수가 담긴 dp[i]를 
        # dp[j]까지의 최대 전깃줄 개수에 1을 더한 수와 비교하여 더 큰 수로 갱신해준다.
        if wire[j][1] < wire[i][1]:
            dp[i] = max(dp[i],dp[j]+1)

# 전체 개수에서 최장 증가 수열 개수를 빼주면 된다.
print(n - max(dp))

문제 출처

2565번: 전깃줄