문제
https://www.acmicpc.net/problem/2565
접근
- 전깃줄이 교차하지 않으려면 첫 번째 전봇대의 원소 x, y에 대해 x < y인 경우 연결된 두 번째 전봇대의 원소 f(x), f(y)가 f(x) < f(y)를 만족해야 한다. (f는 문제에서 주어진 연결 정보)
- 따라서 한 전봇대를 기준으로 정렬한 뒤, 다른 전봇대에서 만들 수 있는 가장 긴 오름차순 수열의 길이를 구하면 되므로 LIS를 이용하기로 했다.
풀이
n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
a.sort()
# LIS
# d[i]: a[i][1] 을 마지막으로 하는 가장 긴 증가하는 부분 수열의 길이
# d[i] = max(d[j] + 1), 0 <= j < i & a[j][1] < a[i][1]
d = [1] * n
for i in range(1, n):
for j in range(i):
if a[i][1] > a[j][1] and d[i] < d[j] + 1:
d[i] = d[j] + 1
print(n - max(d))
'Python > Coding Test' 카테고리의 다른 글
13168 내일로 여행 (0) | 2022.02.23 |
---|---|
1421 나무꾼 이다솜 (0) | 2022.02.23 |
15728 에리 - 카드 (0) | 2022.02.22 |
16933 벽 부수고 이동하기 3 (0) | 2022.02.22 |
9996 한국이 그리울 땐 서버에 접속하지 (0) | 2022.02.17 |