백준 7570. 줄 세우기

tose33 2023. 10. 7. 16:13

7570번: 줄 세우기

입력은 2 개의 줄로 이루어져 있다. 첫 줄에는 어린이 수를 나타내는 정수가 주어진다. 둘째 줄에는 처음에 줄서있는 어린이들의 번호가 차례대로 주어진다. 주어진 번호들 사이에는 공백이 하

www.acmicpc.net

어린이의 번호는 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] 를 비교해서 풀수 있다.