블록 나누기

$i$번째 원소 뒤에서 블록을 나눌 수 있다고 하자. 그러면 그 앞에 있는 모든 블록을 정렬하여 이어 붙인 결과는 정렬된 전체 순열의 앞 $i$개 원소와 같아야 한다. 따라서 $P_1,P_2,\cdots,P_i$는 정확히 $1,2,\cdots,i$로 이루어져 있어야 한다.

순열의 원소는 모두 서로 다르므로, 다음 두 조건은 서로 동치이다.

• $P_1,P_2,\cdots,P_i$가 정확히 $1,2,\cdots,i$로 이루어져 있다.
• $\max(P_1,P_2,\cdots,P_i)=i$이다.

두 번째 조건이 성립하면 앞의 $i$개 원소는 모두 $i$ 이하이고, 서로 다른 $i$개의 원소이므로 반드시 $1$부터 $i$까지를 정확히 한 번씩 포함한다.

따라서 왼쪽부터 순열을 읽으며 지금까지의 최댓값을 관리하고, 그 최댓값이 현재 위치 $i$와 같은 모든 지점에서 블록을 나누면 된다. 이러한 지점을 모두 선택해도 인접한 두 경계 사이의 블록은 필요한 연속된 값 구간을 정확히 포함하므로 모든 분할 조건을 만족한다. 가능한 모든 경계를 선택하므로 블록 개수도 최대이다.

시간 복잡도는 $O(N)$이고, 입력을 저장하지 않으면 추가 공간 복잡도는 $O(1)$이다.

Solution written by GPT5.6