백준 GOLD 5 [2565번] 전깃줄 {언어 : Python} [다시 풀어 보기]

문제 링크

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

정답 코드

import sys
input = sys.stdin.readline
n = int(input())
lines = sorted([list(map(int, input().split())) for _ in range(n)], key=lambda x:x[1])
dp = [1] * n
for i in range(1, n):
    si, ti = lines[i]
    for j in range(i):
        sj, tj = lines[j]
        if sj < si:
            dp[i] = max(dp[j]+1, dp[i])

print(n - max(dp))

풀이 방법

 

1. 입력 처리 및 정렬
   • (시작점, 끝점)을 입력받고 끝나는 지점 기준으로 정렬한다.
   • 정렬은 그리디 + DP 조합을 활용하기 위한 사전 작업이다.
2. DP 배열 정의 및 초기화
   • dp[i]는 i번째 선분을 포함했을 때 겹치지 않는 최대 선분 개수를 저장한다.
   • 모든 값은 최소 1이므로 [1] * n으로 초기화한다.
3. DP 점화식 적용
   • 이중 반복문을 돌며 sj < si 조건을 만족하는 경우 dp[i] = max(dp[j] + 1, dp[i])로 갱신한다.
   • 즉, 선분이 겹치지 않는 경우 최대 선택 개수를 업데이트한다.
4. 결과 출력
   • max(dp)는 최대 겹치지 않는 선분 개수를 의미한다.
   • 전체 개수 n에서 max(dp)를 빼면, 제거해야 할 최소 선분 개수가 된다.

lis 알고리즘

from bisect import bisect_left

import sys
input = sys.stdin.readline
n = int(input())
lines = sorted([list(map(int, input().split())) for _ in range(n)], key=lambda x:x[1])

lis = []
for si, _ in lines:
    pos = bisect_left(lis, si)  # lis에서 si가 들어갈 위치 찾기
    if pos == len(lis):
        lis.append(si)  # 새로운 원소 추가
    else:
        lis[pos] = si  # 기존 원소 교체 (LIS 유지)

print(n - len(lis))  # 제거해야 하는 최소 선분 개수

 

느낀점

 

1. 기존 코드 (O(n^2)): DP를 이용해 최대 겹치지 않는 선분 개수를 구한다.
2. 개선 코드 (O(n log n)): 이분 탐색 기반 LIS 알고리즘을 활용하여 최적화 가능하다.
3. print(n - max(dp))를 통해 제거해야 할 최소 선분 개수를 출력하는 것이 핵심이다.
4. 겹치는 부분을 구하려고 했으나 안 겹치는 부분의 개수를 구하면 쉬워지는 문제였다.