[Kotlin] 백준 1806 : 부분합

문제 링크

1806번: 부분합

---

---

문제 해설

부분합과 투 포인터가 결합된 문제다. 부분합에 대한 내용은 아래 포스트를 참고하면 좋다.

링크 : 누적합(Prefix Sum)과 부분합(Partial Sum) with Kotlin

누적합을 저장할 크기가 \(n+1\)인 배열을 선언하고 1번째 인덱스부터 누적합을 저장해나간다. 이후 투 포인터를 사용해서 배열 위를 이동하기 시작한다. start부터 end까지의 합이 \(S\) 이상이라면 기존 구간 길이의 최소값과 현재 구간 길이를 비교하여 최소값을 갱신한 후 start를 증가시키고, \(S\)보다 작다면 end를 증가시킨다. 모든 과정을 진행했을 때 minLength가 초기값 그대로라면 부분합이 \(S\) 이상인 구간은 존재하지 않는 것이므로 0을 출력하고 그 외의 경우에는 minLength를 출력한다.

---

Code

import java.util.StringTokenizer

fun main() = with(System.`in`.bufferedReader()) {
    val (n, s) = readLine().split(' ').map { it.toInt() }
    val st = StringTokenizer(readLine())
    val sum = IntArray(n + 1)
    repeat(n) {
        sum[it + 1] = sum[it] + st.nextToken().toInt()
    }
    var minLength = 100001
    var start = 0
    var end = 1
    while (end <= n) {
        if (sum[end] - sum[start] >= s) {
            minLength = minOf(minLength, end - start)
            start++
        } else {
            end++
        }
    }
    println(if (minLength == 100001) 0 else minLength)
}