백준 7570. 줄 세우기

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

7570번: 줄 세우기

 

어린이의 번호는 1,2,3...N 으로 순차적으로 정렬되어야 한다.

그 말은 이미 1만큼 증가하도록 정렬되어 있는 친구들은 가만히 있으면 되고, 나머지를 양끝으로 움직이면 된다.

 

최초에 5,2,4,1,3 이면 위 조건에 맞는 친구들인 5,2,4,1,3 이다. 

2와 3은 고정시키고 나머지를 앞 뒤로 움직이면 된다는 것을 볼 수 있다.

 

그래서 이 문제는 Longest Increasing Sequence 와 비슷한데, 그냥 증가하기만 하면 안되고 1 차이로 증가해야 한다.

그리고 N의 최댓값이 100만이기 때문에 그냥 O(N^2) LIS 알고리즘으로는 풀수 없다.

 

pos[i] = i번째 어린이가 최초에 있는 위치를 저장해놓으면 pos[i-1] 과 pos[i] 를 비교해서 풀수 있다.