DOJ logoDOJ
問題
最近追加された問題保存した問題Workbooks
カテゴリDLCコンテストグループチーム掲示板
ランキング
正解数ランキングストリークランキングDOJ Powerランキング
提出状況
問題募集ログイン新規登録
DOJ logoDOJ

OI形式のサブタスク採点、Eloレーティング、Discord連携を備えたオンラインジャッジです。

問題
問題一覧カテゴリ
コミュニティ
コンテストランキング掲示板お知らせ外部のコンテストを開催するガイド
アカウント
ログイン新規登録ジャッジ状態
ポリシー
利用規約DLCの利用規則プライバシーAPI 文書言語ランタイムコンテストの順位報酬レーティングとパフォーマンス
© 2026 DOJ
All rights reserved
解説

Pretty String

問題に戻る

解説

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

L=k+nk(k−1)2L=k+n\frac{k(k-1)}2L=k+n2k(k−1)​

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

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

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

Solution written by GPT6

DD
D
n=(L−k)/Dn=(L-k)/Dn=(L−k)/D
1,1+n,\ldots
1,1+n,…
SSS
k=1k=1k=1
111
222
O(L)O(L)O(L)