https://www.acmicpc.net/problem/2565
시간 1초, 메모리 128MB
input :
- n (1 ≤ n ≤ 100)
- A전봇대와 연결되는 위치의 번호 B전봇대와 연결되는 위치의 번호
output :
-
합선의 위험이 있어 이들 중 몇 개의 전깃줄을 없애 전깃줄이 교차하지 않도록 만들려고 한다.
-
전깃줄이 전봇대에 연결되는 위치는 전봇대 위에서부터 차례대로 번호가 매겨진다.
-
없애야 하는 전깃줄의 최소 개수를 구하는
이 문제의 경우도 아까 봤던 반도체 설계와 비슷하다.
예전에는 어떤 문제인지 짐작을 못했던 문제이다.
이런 "꼬여있는" 또는 전봇대 같은 문제에 대한 접근은 숫자를 가지고 사용하는 방식을 생각해 봐야겠다.
일단 입력값에 대해 정렬이 필요하다.
그림과 동일한 순서가 필요하기 때문에 그렇다.
그럼 그 순서에 대해서 예를 들어보면
맨 처음에는 [8]
그 다음에는 [2]
9는 추가 되어도 꼬이지 않으니까 [2, 9]
이분 탐색을 사용할 거기 때문에 인덱스는 계속 업데이트 하면서 [1, 9]
4의 위치는 9보다 앞 설 수 있으니까 [1, 4]
그 다음부터는 그냥 다 추가 할 수 있다. [1, 4, 6][1, 4, 6, 7]
[1, 4, 6, 7, 10]
이렇게 꼬이지 않도록 할 수 있다.
import sys
from bisect import bisect_left
n = int(sys.stdin.readline())
data = []
for _ in range(n):
a, b = map(int, sys.stdin.readline().split())
data.append((a, b))
data.sort()
temp = [data[0][1]]
for i in range(1, len(data)):
if temp[-1] < data[i][1]:
temp.append(data[i][1])
else:
idx = bisect_left(temp, data[i][1])
temp[idx] = data[i][1]
print(n - len(temp))
