[Kotlin] 백준 31882 : 근수

문제 링크 : https://www.acmicpc.net/problem/31882

---

문제 해설

주어진 문자열에서 연속된 2로만 이뤄진 부분 문자열(이하 근수)들을 추출하여 점수를 구해야합니다.

 

근수들은 문자열 전체를 순회하면서 현재 숫자가 2라면 현재까지 구해진 부분 문자열에 2를 추가하고, 그 외의 경우에는 현재까지 구해진 부분 문자열을 리스트에 추가한 후 부분 문자열을 초기화하는 방법으로 구할 수 있습니다.

 

문자열을 모두 순회한 후 구해놓은 부분 문자열이 있다면 리스트에 추가해줍니다.

for (num in s) {
    if (num == '2') {
        sb.append(2)
        continue
    }
    if (sb.isEmpty()) continue
    list.add(sb)
    sb = StringBuilder()
}
if (sb.isNotEmpty()) list.add(sb)

근수들을 모두 구했으니 이제 근수 점수를 구해야 합니다.

 

근수 점수는 각 근수들의 길이를 length라고 할 때 아래와 같이 계산이 됩니다.

$$\textrm{score}=\textrm{length}\times1+(\rm{length}-1)\times2+\cdots+2\times(\textrm{length}-1)+1\times\textrm{length}$$

 

이를 확인해보기 위해 아래 length가 5인 22222의 경우를 한번 봅시다.

22222의 경우는 위와 같이 근수들을 쪼개서 근수 점수를 계산하게 됩니다. 즉, \(\textrm{score}=5\times1+4\times2+3\times3+2\times4+1\times5\)가 되는거죠.

이를 반복문으로 나타내면 아래처럼 표현할 수 있습니다.

for (i in 1..length) {
    result += (length - i + 1) * i
}

이대로만 해도 통과하는데는 지장이 없지만 반복문을 수학적으로 풀어서 한번에 계산까지 해봅시다.

 

반복문을 수학적으로 나타내면 아래 수식을 얻을 수 있습니다. \(n=\textrm{length}\)입니다.

$$\textrm{score}=\sum_{i=1}^{n}(i(n-i+1))$$

분배법칙을 적용하여 수식을 전개해줍니다.

$$\textrm{score}=\sum_{i=1}^{n}(ni-i^2+i)$$

이제 모든 항이 덧셈과 뺄셈으로 나눠졌으니 식을 정리해봅시다.

$$\textrm{score}=(n+1)\sum_{i=1}^{n}i-\sum_{i=1}^{n}i^2$$

이제 각 급수를 전개합니다.

$$\textrm{score}=(n+1)\times\frac{n(n+1)}{2}-\frac{n(n+1)(2n+1)}{6}$$

\((n+1\)이 공통항으로 존재하니 묶어줍니다.

$$\textrm{score}=(n+1)(\frac{n(n+1)}{2}-\frac{n(2n+1)}{6})$$

괄호 안의 수식을 계산해서 정리해줍니다.

$$\textrm{score}=(n+1)\times\frac{n^2+2n}{6}$$

마지막으로 공통되는 \(n\)을 묶어주고 식을 정리하면 최종 수식을 얻을 수 있습니다.

$$\textrm{score}=\frac{n(n+1)(n+2)}{6}$$

즉 각 근수들의 근수 점수는 \(\textrm{score}=\frac{\textrm{length}(\textrm{length}+1)(\textrm{length}+2)}{6}\)라는 것을 알 수 있습니다.

 

위에서 구한 근수 리스트를 모두 순회하면서 해당 식으로 근수 점수를 구해 더해주면 최종 결과를 얻을 수 있습니다.

Code

fun main() = with(System.`in`.bufferedReader()) {
    readLine()
    val s = readLine()
    var sb = StringBuilder()
    val list = ArrayList<StringBuilder>()
    for (num in s) {
        if (num == '2') {
            sb.append(2)
            continue
        }
        if (sb.isEmpty()) continue
        list.add(sb)
        sb = StringBuilder()
    }
    if (sb.isNotEmpty()) list.add(sb)
    var result = 0L
    for (num in list) {
        val length = num.length.toLong()
        result += length * (length + 1) * (length + 2) / 6
    }
    println(result)
}