[백준 2565] 전깃줄 - python (solved.ac - 골드 5)

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

2565번: 전깃줄

풀이

문제를 보았을 때 알 수 있는 힌트

문제를 통해서 겹치는 구간을 없애기만 하면 되는 문제이다. 다시 말해서 최장 증가 부분 수열(LIS)로 문제를 풀면 된다.

다음에 관련해서 알고리즘을 작성해놓아야 좋을듯하다.

 

두가지 방식으로 풀었는데 dp와 이분탐색으로 문제를 해결하였다.

 

import sys
input = sys.stdin.readline

n = int(input())
n_list = []
for i in range(n):
    n_list.append(list(map(int,input().split())))

n_list.sort()

# dp로 풀어보기
dp = [1]*n
for i in range(n):
    for j in range(i):
        if n_list[i][1]>n_list[j][1] and dp[i]<dp[j]+1:
            dp[i]= dp[j]+1
print(n - max(dp))

 

# 전기줄
import sys
from bisect import bisect_left
input = sys.stdin.readline

n = int(input())
n_list = []
for i in range(n):
    n_list.append(list(map(int,input().split())))

n_list.sort()

# 이분 탐색으로 풀어보기
x= [n_list[0][1]]
dp = [1]
for i in range(1, n):
    if n_list[i][1]>x[-1]:
        x.append(n_list[i][1])
        dp.append(dp[-1]+1)
    else:
        idx = bisect_left(x,n_list[i][1])
        x[idx] = n_list[i][1]
print(n - max(dp))

모두 이상없이 결과가 나왔고 효율적인 면에서는 이분 탐색이 효율적이다.

다만 이번 문제에서는 dp가 빨랐다.

https://github.com/dydwkd486/coding_test/blob/main/baekjoon/baekjoon2565.py

GitHub - dydwkd486/coding_test: 코딩테스트 공부한 내용 정리