[백준] 전깃줄 2565번 (python) LSB

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

 

풀이 방법

전깃줄이 갖아 길게 안 꼬이는 경우를 찾으면 된다.

와이어 A를 기준으로 연결된 쌍을 정렬한 뒤 B의 최장 증가 부분 수열을 구한 후 이를 원본 쌍에서 빼주면 된다.

 

1. 먼저 모든 연결된 쌍을 입력받는다.

2. 와이어 A를 기준으로 정렬한다.

3. 와이어 B를 저장하는 배열을 생성한다.

4. 와이어 B를 탐색하며 만약 최장증가 부분 수열의 임시 배열인 lsb_arr의 마지막 원소보다 크다면 뒤에 추가한다.

5. 크지 않다면 lsb_arr에서 현재 원소가 들어갈 인덱스를 이분탐색을 통해 구한 후 추가해 준다.

6. lsb_arr의 길이를 구하면 이것이 최장 증가 부분 수열의 길이이다. 

N = int(input())
wire = [] ## 전체 와이어
wirt_b = [] ## 와이어 B
for i in range(N):
    a, b = map(int, input().split())
    wire.append([a, b])

wire.sort(key = lambda x : x[0]) ## 와이어 A를 기준으로 오름차순 정렬
for i in range(len(wire)):
    wirt_b.append(wire[i][1]) 

lsb_arr = [wirt_b[0]]

def binary(num):
    left, right = 0, len(lsb_arr)-1
    mid = 0
    while(left <= right): 
        mid = (left + right) // 2
        if lsb_arr[mid] == num:
            return mid
        if lsb_arr[mid] < num < lsb_arr[mid+1]:
            return mid+1
        elif lsb_arr[mid] > num:
            right = mid - 1
        else:
            left = mid + 1  
    return mid
def LSB():
    ans = 0
    for i in range(N):
        target = wirt_b[i]
        if lsb_arr[-1] < target: ## 마지막 원소 보다 크면 
            lsb_arr.append(target) ## 마지막 원소에 추가
        else: 
            idx = binary(target) ## 사이 인덱스 탐색
            lsb_arr[idx] = target          
    return len(lsb_arr) ## 최장 승가부분 수열 길이 리턴 

cnt = LSB() ## 최장 증가 수열 구하기
print(len(wire) - cnt) ## 전체 배열 길이에서 - 가장 긴 수열