import sys
input = sys.stdin.readline
N = int(input().rstrip())
wire = [list(map(int, input().rstrip().split(' '))) for _ in range(N)]
dp = [1] * N
wire.sort(key=lambda x:x[0])
for i in range(N):
for j in range(i):
if wire[i][1] > wire[j][1]:
dp[i] = max(dp[i], dp[j]+1)
print(N-max(dp))
LIS(최장 증가수열)을 이용하는 문제
wire
에 넣는다.[2, 4, 6, 7, 10]
또는 [1, 4, 6, 7, 10]
이 나온다. 연결할 수 있는 값들이다.전봇대A | 전봇대B | 증가수열 |
---|---|---|
1 | 8 | 8 |
2 | 2 | 2 |
3 | 9 | (2, 9) (8, 9) |
4 | 1 | (2, 9) (8, 9) |
6 | 4 | (2, 9) (8, 9) (2, 4) (1, 4) |
7 | 6 | (2, 9) (8, 9), (2, 4, 6), (1, 4, 6) |
9 | 7 | (2, 9) (8, 9) ... (2, 4, 6, 7) |
10 | 10 | (2, 9) (8, 9)... (2, 4, 6, 7, 10) (1, 4, 6, 7, 10) |