https://www.acmicpc.net/problem/2565
재밌는 LIS 유형 문제가 있어 정리해보았다.
먼저 아래와 같이 입력이 주어진다고 하면
1 8
3 9
2 2
4 1
6 4
10 10
9 7
7 6
아래와 같은 모양으로 전깃줄이 엉켜 있는 것이다
근데 여기서 (6, 4)
로 이어져 있는 전깃줄의 기준에서 보면
(6, 4)
까지 있을 때 엉켜 있지 않은 전깃줄의 최대 개수는 아래와 같이 2가지 경우의 수를 생각할 수 있고
결과적으로 (6, 4)
까지 전깃줄에서 볼 때 최대 전깃줄의 개수는 2라는 것을 알 수 있다
또 (7, 6)
전깃줄의 기준에서 봤을 때 아래와 같이 2가지의 경우의 수를 생각해 볼 수 있고
이는 방금 위에서 본 (6, 4)
전깃줄의 최대값에 + 1((7, 6)
포함) 인 값으로 말할 수 있다
따라서 이를 일반화해 보면 현재까지() 전깃줄로 구성된 전깃줄의 최대 개수는 이전 전깃줄() 구성의 최개 개수 + 1 로 일반화가 가능하다
따라서 문제는 전깃줄이 최대로 엉키지 않도록 하는 잘라야할 전깃줄의 개수이므로 전체 전깃줄 셋의 개수()에서 빼주면 된다
이를 파이썬 코드로 표현하면 아래와 같다
import sys
N = int(input())
v = []
for i in range(N):
a = list(map(int, input().split()))
v.append(a)
v.sort()
dp = [1] * (N)
for i in range(1, N):
for j in range(0, i):
if (v[i][0] > v[j][0] and v[i][1] > v[j][1]) or \
(v[i][0] < v[j][0] and v[i][1] < v[j][1]):
dp[i] = max(dp[i], dp[j] + 1)
print(N - max(dp))