[백준] 1806번: 부분합 - Kotlin[코틀린]

문제

 

1806번: 부분합

 

---

풀이

 

 시작과 끝을 가리키는 start와 end 포인터를 활용하여 탐색한다. 두 포인터는 초기에 0으로 초기화되며, 두 포인터 사이의 값의 합과 찾으려는 값을 비교하면서 탐색한다.

 

 만약 현재까지의 누적 합이 찾으려는 값보다 작다면 end 포인터를 뒤로 이동시킨다. 만약 end 포인터가 이미 배열의 끝까지 도달했다면 반복문을 종료한다. 누적 합이 찾으려는 값보다 크거나 같다면 현재 구간의 길이를 갱신하고 start 포인터를 뒤로 이동시킨다.

 

---

 

코드

 

import java.util.*

fun main() {
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()

    val st = StringTokenizer(br.readLine())
    val num = st.nextToken().toInt()
    val sum = st.nextToken().toInt()
    val arr = br.readLine().split(' ').map { it.toInt() }
    var cnt = Int.MAX_VALUE
    var tmp = 0
    var start = 0
    var end = 0

    while(true) {
        if(tmp >= sum) {
            cnt = minOf(cnt, end - start)
            tmp -= arr[start++]
        } else {
            if(end == num) break
            tmp += arr[end++]
        }
    }

    bw.write(if(cnt == Int.MAX_VALUE) "0" else "$cnt")
    bw.flush()
    bw.close()
    br.close()
}