BOJ 2565(전깃줄)풀이

solved.ac 티어 : 실버 1

www.acmicpc.net/problem/2565

2565번: 전깃줄

 

이문제는 joseph0528.tistory.com/25

BOJ 2352(반도체 설계)풀이

반도체 설계 문제와 매우 흡사하다.

반도체 설계는 교차하지 않는 선의 최대 개수고 전깃줄은 교차하지 않는 선의 개수가 최대가 되게 할 때 없애는 전깃줄의 개수이다. 즉 n-반도체 설계 답 = 전깃줄 문제의 답이 된다.

이제 그럼 전깃줄입력을 반도체 설계처럼 바꿔주면 된다.

반도체 설계는 i번째와 입력값이 연결되어있는 것이기 때문에 전깃줄 문제도 한쪽을 잡고 정렬해서 순서대로 배열에 값을 넣어주고 LIS를 해주면 된다.

import sys
sys.setrecursionlimit(1000001)
a=int(input())
pq=[]
for i in range(a):c,d=map(int,input().split());pq.append([d,c])
pq.sort()
l=[]
for i in range(a):l.append(pq[i][1])
#print(l)
t=[0]
def lower_bound(n):
    start=0
    end=len(t)-1
    while start < end:
        m=(start+end)//2
        if t[m]<n:
            start=m+1
        else:
            end=m
    return end
for x in range(a):
    if t[len(t)-1] < l[x]:
        t.append(l[x])
    else:
        t[lower_bound(l[x])]=l[x]
print(a-len(t)+1)