[AC] 2565 전깃줄

출처 : https://www.acmicpc.net/problem/2565

정답 : https://github.com/stemp12/study/blob/master/acmicpc.net/2016.12/2565.cpp

이 문제는 초등부 올림피아드 문제이다. 심지어 거의 10년전에 출제된 문제인데... 난 이걸 최근에 알았는데... 

내가 왜 구직활동이 힘든지 이해가 된다. 전국에는 뛰어난 인재가 참 많은거 같다.

근데 뭐 나도 LIS를 사용하니 금방 풀긴 했다. 물론 LIS인지 빨리 파악하는게 매우 중요하다.

나는 다음과 같은 방법으로 접근했다.

1. 우선 겹치지 않아야 한다. 그러면 A를 기준으로 봤을때 B가 순차적이면 되면 될거같다.

2. A를 기준으로 입력을 정렬해보자. 그럼 예제는 다음과 같이 된다.

1 8
2 2
3 9
4 1
6 4
7 6
9 7
10 10

이렇게 보니 딱 사이즈가 나온다. 위에 3개를 쳐내면 4부터 최장증가수열이 만들어 진다.

즉, 나는 최장증가수열을 구하고 n에서 빼면 되는 것이다.

문제는 많이 어려워보이지만 실질적으로는 별거 없는 것이다.