[Kotlin] 백준 25916 : 싫은데요

문제 링크

25916번: 싫은데요

---

---

문제 해설

부분합의 최대치 중 M 이하인 값을 구하는 문제다. 문제에 햄스터가 막을 구멍은 반드시 연속되어야 한다는 제한이 있기 때문에 투 포인터를 이용하여 풀 수 있다.

 

투 포인터는 이름 그대로 두 개의 점이 배열 위를 이동하면서 주어진 조건에 맞는 답을 찾아가는 방법이다. 본 문제에서는 독의 첫 번째 구멍부터 마지막 구멍까지 햄스터가 계속 몸을 늘리거나 줄여가면서 답을 찾을 수 있다. 주어진 예제를 그림으로 표현해보자.

그림을 보면 현재 햄스터가 막은 구멍 크기의 합계가 조건보다 작은 경우엔 햄스터가 오른쪽으로 늘어나고, 햄스터가 막은 구멍 크기의 합계가 조건보다 큰 경우엔 햄스터가 오른쪽으로 줄어들면서 이동하고 있다. 이렇게 이동하다가 햄스터가 마지막 구멍까지 막게 되면 검사를 종료하고 조건에 맞는 최대값을 출력하게 된다. 즉, 이 경우에는 햄스터의 다리가 부분 배열의 시작점이 되고 햄스터의 머리가 부분 배열의 끝점이 된다. 이에 맞게 배열을 순회하면 답을 찾을 수 있다.

---

Code

import java.util.StringTokenizer

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

---

참조 링크

투 포인터(Two Pointer) with Kotlin