728x90
SMALL

import sys; input=sys.stdin.readline
from bisect import bisect_left
N = int(input())
loc = sorted([list(map(int, input().split())) for _ in range(N)])
# LIS를 위해 B 값들 저장
dp = []
# 각 전깃줄이 LIS의 어느 인덱스에 들어갔는지 저장
pos = [0] * N
# 실제 LIS 구하는 과정과 인덱스까지 저장하는 로직 !
for i in range(N):
b = loc[i][1]
idx = bisect_left(dp, b)
if idx == len(dp):
dp.append(b)
else:
dp[idx] = b
pos[i] = idx
len_dp = len(dp)
print(N - len_dp)
# 이번에는 LIS에 포함된 인덱스 역추적하기
need = len_dp - 1
keep = set()
for i in range(N-1, -1, -1):
if pos[i] == need:
keep.add(i)
need -= 1
if need < 0:
break
# 제거해야 할 A 값들
for i in range(N):
if i not in keep:
print(loc[i][0])
왜 이렇게 풀었을까?
- 해당 문제는 LIS(최장 증가 부분 수열) 문제로 유명한 전깃줄 문제입니다.
- 이 문제를 가장 간단하게 푸는 방법은 DP로 접근하는 것인데, DP로 접근하게 되면 최악의 경우, 시간 복잡도가 O(N^2)까지 나오기 때문에, 최적으로 LIS 배열을 늘릴 수 있는 이분 탐색을 선택했습니다.
- LIS는 일단 dp[-1]보다 들어오는 값이 더 크면, dp에 들어오는 값을 추가하고, 아니면 이분 탐색으로 들어가야할 위치를 찾아 대체하는 방식으로 풀이하곤 합니다.
- 이 문제는 LIS의 길이뿐만 아니라 제거되는 전깃줄의 인덱스도 함께 요구하고 있기 때문에, LIS의 따른 인덱스까지 함께 저장해 이 인덱스 배열을 역추적함으로써 오름차순으로 출력할 수 있게 구현하였습니다.
- 기존의 전깃줄 문제에 더해 인덱스를 다시 빼오는 요구사항이 이 문제를 플레로 만들지 않았나... 싶습니다.
- 그리고 심화 문제로 갈수록 이분 탐색과 bisect 모듈의 소중함을 동시에 느끼고 있는 것 같습니다.
728x90
LIST
'알고리즘 문제 풀이 > Class (solved.ac)' 카테고리의 다른 글
| 🏫 낚시왕 (Class 5++) (0) | 2025.10.27 |
|---|---|
| 🏫 벽 부수고 이동하기 4 (Class 5++) (0) | 2025.03.04 |
| 🏫 공항 (Class 5++) (0) | 2025.02.26 |
| Class 2 (팩토리얼 0의 개수 ~ 좌표 정렬하기) (4) | 2023.12.20 |
| Class 2 (달팽이는 올라가고 싶다 ~ 영화감독 숌) (0) | 2023.12.18 |