[다이나믹 프로그래밍] ▲ 2565번 - 전깃줄

[백준] 2565번 - 전깃줄

(한줄평) 최장 증가 부분 수열과 유사한 문제라고 생각했지만 막상 잘 해결이 안됐던 문제.. 복습이 필요하다!!

유사 문제: 11053

https://hseungyeon.tistory.com/304

[다이나믹 프로그래밍] ▲ 11053번 - 가장 긴 증가하는 부분 수열

 

풀이 시간: 30분 이내

1) 문제 해결 아이디어

전깃줄의 개수와 전깃줄들이 두 전봇대에 연결되는 위치의 번호가 주어질 때, 남아있는 모든 전깃줄이 서로 교차하지 않게 하기 위해 없애야 하는 전깃줄의 최소 개수를 구하는 문제다. 이는 모든 전깃줄이 서로 교차하지 않게하는 부분 전깃줄의 최대 개수를 구하는 문제와 같다.

이 문제는 최장 증가 부분 수열을 구하는 문제로 치환하여 푸는 것을 깨닫는게 중요하다. 나도 처음엔 LIS 알고리즘을 사용해서 풀어야한다는 것은 알았는데 그 이후에 어떤 식으로 검사를 해야할지 감을 잘 못잡았다. 여기서 핵심은 전봇대 A(0열)을 기준으로 오름차순 정렬하고 전봇대 B(1열)의 최장 증가 부분 수열을 구하는 것이다!!

 

Q. 전봇대 A(0열)을 기준으로 오름차순 정렬하는 이유는??

전깃줄이 꼬이지 않는 조건은 2가지 경우가 있다.

1. 전깃줄 A의 위치 a1 > a2 일 때, 전깃줄 B의 위치 b1 > b2 

2. 전깃줄 A의 위치 a1 < a2 일 때, 전깃줄 B의 위치 b1 < b2

여기서 우리는 편의를 위해 2번을 기준으로 생각하고자 한다. 그러므로 항상 a1 < a2이기 위해서 우리는 전봇대 A(0열)을 기준으로 오름차순 정렬을 하는 것이다!

 

<점화식>

제거해야하는 전깃줄의 최소 개수 = 전체 전깃줄의 개수 - 남아있는 전깃줄이 서로 교차하지 않는 최대 전깃줄의 개수

 

2) 소스코드

import sys
input = sys.stdin.readline

n = int(input())  # 전깃줄 개수
graph = [list(map(int, input().split())) for _ in range(n)]
graph.sort()  # 첫번쨰 

d = [1] * n  # i번째 전깃줄이 마지막인 모든 전깃줄이 교차하지 않게하는 최대 전깃줄의 개수
for i in range(1, n):
  for j in range(i):
    if graph[j][1] < graph[i][1]:
      d[i] = max(d[i], d[j] + 1)
print(n - max(d))  # 모든 전깃줄이 서로 교차하지 않게 하기 위해 없애야 하는 전깃줄의 최소 개수