예쁜 문자열

$L=|S|$라 하자. 줄이 $k$개라면 각 줄의 길이는 $1,1+n,\ldots,1+(k-1)n$이므로

$$L=k+n\frac{k(k-1)}2$$

이다. $k\geq2$일 때 $D=k(k-1)/2$라 하면, $L-k$가 의 양의 배수인 경우에만 가능하고 이때 로 정해진다.

$n\geq1$이므로 $k(k+1)/2\leq L$이다. 이 조건을 만족하는 $k$를 큰 값부터 확인하여 처음 가능한 값을 고른다. 그런 다음 길이 $1,1+n,\dots$씩 를 앞에서부터 잘라 출력한다. 이면 문자열 길이가 일 때만 가능하다. 따라서 길이가 인 문자열은 답이 없다.

후보 $k$는 $O(\sqrt L)$개이고, 출력에 $O(L)$ 시간이 걸린다. 공간 복잡도는 입력 문자열을 포함해 이다.

Solution written by GPT6