import sys
input = sys.stdin.readline
from bisect import *
N = int(input())
animal = set()
for _ in range(N):
i,x,y = map(int,input().split())
animal.add((-x,y))
animal = sorted(animal)
DP = [0]
for a,b in animal:
if b>=DP[-1]:
DP.append(b)
else:
DP[bisect_right(DP,b)] = b
print(len(DP)-1)
LIS로 해결하였다.
아이디어를 떠올리기 쉽지 않았던 문제였다. 처음에는 정렬+스택 문제라고 생각했는데, 정렬+스택으로 풀 수 없다는 사실을 깨달았다. LIS를 이용한다는 아이디어만 떠올리면 구현자체는 매우 쉽지만, LIS라는 사실을 잘 숨겨놓은 문제이다.
풀이를 설명하면,
1. 각각 동물의 시작과 끝 좌표를 튜플로 set에 저장하여 중복을 제거하고 정렬한다. (이때 시작좌표는 음수로 저장한다)
2. 동물의 끝 좌표에 대해서 LIS의 길이를 구한다. (이때 LIS는 증가 뿐만아니라 같아도 된다)
먹이사슬에 속한 모든 동물들은 시작좌표는 증가, 끝좌표는 감소하게 된다. 따라서 시작좌표를 기준으로 정렬하고, 끝좌표에 대해서 LDS (가장 긴 감소하는 부분수열)의 길이를 구해주면 된다. 나는 편의를 위해 시작좌표를 음수로 저장하고 LIS의 길이를 구해주었다.
오늘의 교훈) LIS를 상황에 따라 적절하게 활용하자