Baekjoon 2568. 전깃줄 - 2 / Python

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

문제 설명

주어진 두 전봇대 사이에 연결된 전깃줄이 교차하지 않도록 하기 위해 최소 개수의 전깃줄을 제거해야 합니다. 각 전깃줄의 연결 정보를 바탕으로, 전깃줄이 교차하지 않는 최장 증가 부분 수열(LIS)을 찾아야 합니다. 이 문제는 LIS를 활용하여 해결할 수 있습니다.

알고리즘 설명

1. 입력 처리 및 정렬:
   • 전깃줄의 정보를 입력받아 정렬합니다.
   • 두 전봇대 A와 B의 연결 위치 정보를 입력받아 전봇대 A의 위치를 기준으로 정렬합니다. 이는 전봇대 B의 위치에서 LIS를 찾기 위함입니다.
2. LIS를 이용한 전깃줄 제거:
   • 정렬된 전깃줄 정보를 바탕으로 전봇대 B의 위치 값들에 대해 LIS를 구합니다.
   • LIS의 길이를 통해 남아있는 전깃줄의 개수를 파악합니다.
   • 전체 전깃줄 개수에서 LIS의 길이를 빼면 제거해야 하는 전깃줄의 최소 개수를 구할 수 있습니다.
3. LIS 구성 요소 추적:
   • dp 배열을 이용해 각 전깃줄이 LIS의 어느 위치에 해당하는지 저장합니다.
   • dp 배열을 역순으로 탐색하여 실제 LIS 수열에 포함된 전깃줄을 추적합니다.
4. 결과 출력:
   • 제거해야 하는 전깃줄의 개수를 출력합니다.
   • 제거해야 하는 전깃줄의 위치를 오름차순으로 출력합니다.

import sys
input = sys.stdin.readline

# 이진 탐색을 통해 LIS 배열의 적절한 위치를 찾는 함수
def binary_search(s, e, lis, goal):
    while s <= e:
        m = (s + e) // 2  # 중간 인덱스 계산
        if lis[m] >= goal:  # 중간 값이 goal보다 크거나 같으면 오른쪽 부분 탐색
            e = m - 1
        else:  # 중간 값이 goal보다 작으면 왼쪽 부분 탐색
            s = m + 1
    return s  # goal이 삽입될 위치 반환

# 전깃줄의 개수 입력
n = int(input())

# 전깃줄의 정보를 담을 리스트
arr = []
for _ in range(n):
    x, y = map(int, input().split())  # 전봇대 A와 B의 연결 위치 입력
    arr.append((x, y))  # (A의 위치, B의 위치) 튜플로 저장

# 전봇대 A의 위치를 기준으로 정렬
arr.sort()

# LIS를 구성하는 전깃줄의 수를 저장할 리스트
dp = [-1] * n

# LIS를 구성하기 위해 B의 위치를 담을 배열 (최소 전깃줄 제거를 위한 배열)
lis = [arr[0][1]]  # 첫 번째 전깃줄의 B의 위치로 초기화
dp[0] = 0  # 첫 번째 전깃줄의 dp 값은 0 (LIS의 첫 원소로 시작)

# 1부터 n-1까지의 전깃줄을 처리
for i in range(1, n):
    if lis[-1] < arr[i][1]:  # 현재 전깃줄의 B 위치가 LIS의 마지막 값보다 크면
        lis.append(arr[i][1])  # LIS에 새로운 원소 추가
        dp[i] = len(lis) - 1  # 현재 전깃줄의 dp 값은 LIS의 길이 - 1
    else:
        idx = binary_search(0, len(lis) - 1, lis, arr[i][1])  # 이진 탐색으로 적절한 위치 찾기
        lis[idx] = arr[i][1]  # 해당 위치의 값 갱신
        dp[i] = idx  # 현재 전깃줄의 dp 값은 찾아낸 위치의 인덱스

# LIS의 길이를 구한 후, 제거해야 하는 전깃줄의 수를 계산
lis_length = len(lis)
print(n - lis_length)  # 제거해야 하는 전깃줄의 개수 출력

# LIS에 포함되지 않은 전깃줄을 추적하여 제거할 전깃줄의 A 위치를 구함
to_remove = []
now = lis_length - 1  # 현재 LIS의 끝 위치를 설정

# dp 배열을 역순으로 탐색하여 LIS의 구성 요소를 찾아냄
for i in range(n - 1, -1, -1):
    if dp[i] == now:  # 현재 전깃줄이 LIS의 끝 위치와 일치하면
        now -= 1  # LIS의 다음 끝 위치로 이동
    else:
        to_remove.append(arr[i][0])  # LIS에 포함되지 않은 전깃줄의 A 위치를 저장

# 제거할 전깃줄의 A 위치를 오름차순으로 정렬
to_remove.sort()
# 제거할 전깃줄의 A 위치를 출력
for a in to_remove:
    print(a)