문제 접근
전봇대에 번호를 입력받아서 교차되는 전깃줄이 없게끔 하고 싶을 때 없애야 하는 전깃줄의 최소 개수를 출력하는 문제.
A 전봇대에 숫자를 1,2,3,4, ...10 에서 차례로 B로 쏜다고 할 때
f(A1) < f(A2) 가 성립하면 된다. ( = 이 들어가지 않는 이유는 문제에서 같은 위치에 두 개 이상의 전깃줄이 연결될 수 없다고 명시했기 때문이다. )
A의 순서를 정렬한 뒤 B순서를 가장 긴 증가하는 순열 (LIS) 로 정렬하면 문제를 풀 수 있다.
해답 및 풀이
import sys
n = int(sys.stdin.readline())
lists = []
dp = [1]*n # i번째 전깃줄을 마지막으로 했을 때의 가장 긴 증가하는 부분 수열의 길이
#dp[2] = 3 → 2번 전깃줄까지 보고, 그걸 마지막으로 하는 증가하는 수열의 최대 길이는 3이라는 뜻
for i in range(n):
a, b = map(int, input().split())
lists.append([a, b])
lists.sort() # a를 기준으로 정렬됨.
for i in range(1, n): # i: 지금 보고 있는 숫자
for j in range(0, i): # j: 그 이전 숫자들 전부 확인
if lists[j][1] < lists[i][1]: # j가 i보다 작으면 (=증가하면) ,뒤 [1] 의 값은 B전봇대의 값을 봐야하기에.
dp[i] = max(dp[i], dp[j]+1) # j에 i를 붙여 수열 하나 늘리기
print(n-max(dp))
Frontend Engineers