[BOJ] 2631번: 줄세우기

https://www.acmicpc.net/problem/2631

 

옮기지 않는 아이는 반드시 increasing sequence를 이루어야 하므로 최대한 적게 옮기려면 LIS의 길이를 알면 됩니다. 즉 주어진 예시 3 7 5 2 6 1 4를 생각해보면 longest increasing sequence인 3 5 6을 제외한 나머지 7 2 1 4를 옮기면 된다는 것을 알 수 있습니다.

N이 매우 작아 O(N^2)으로 짜도 되는데 LIS는 O(NlgN)로 시간복잡도를 낮출 수 있습니다.

https://github.com/encrypted-def/BOJ/blob/master/2631.cpp