[백준] 2631 줄세우기

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

2631번: 줄세우기

---

옮겨지는 아이의 최소한의 수를 구하는 문제입니다.

 

옮길 아이의 최소라는 것은, 옮기지 않을 아이의 최대라고도 할 수 있습니다. 현재 문제는 아이들의 순서 번호를 오름차순으로 정렬해야하기 때문에, 옮기지 않을 아이의 최대 수는 증가하는 부분 수열을 구하는 문제와 동일합니다. 즉, 증가하는 부분 수열의 최대 길이를 구할 수 있다면 최소한으로 옮길 아이들의 수를 구할 수 있을 것입니다.

 

이렇게 정렬되어 있지 않은 배열에서 최대 증가하는 부분 수열의 길이를 구하는 알고리즘을 LIS 알고리즘이라고 합니다. LIS 알고리즘에 대한 설명은 쉽게 찾을 수 있으니 생략합니다.