BOJ 17021 - Cow Poetry

BOJ 17021 - Cow Poetry

지문 해석이 어려운 문제

$dp[i]$ 를 $i$ 길이를 만들 수 있는 경우의 수라고 하고, $dp[k]$ 가 되는 애들은 따로 수를 세주어 $c[i]$ 를 Rhyme Class i 로 끝나는 길이 $k$ 의 line 개수라고 구하자.

알파벳은 최대 $26$개이므로 어떤 알파벳 $x$가 총 $y$개를 가져야 한다면 모든 어떤 Rhyme class를 가질 수 있는 경우의 수는 $\sum_{i=1}^Nc[i]^{y}$ 이므로 이걸 모두 정답에 곱해주면 된다.