[백준 2532번] 먹이사슬 (Python3)

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를 상황에 따라 적절하게 활용하자