[백준] 1806 - 부분합

슬라이딩 윈도우 알고리즘을 사용하여 푸는 문제이다.
"연속된 수들의 부분합" 이라는 문구가 이에 대한 힌트이다.
연속적이어야하므로 입력이 주어진 뒤, 정렬을 해서는 안된다.

풀이

/*
* 0.5초 이므로 5천만까지
* 연속적인 부분합이므로 슬라이딩 윈도우를 활용하여 O(n) 만에 완성시키기
* */
fun `1806 - 부분합`(){
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()
    val (n, s) = br.readLine().split(" ").map { it.toInt() }
    val token = java.util.StringTokenizer(br.readLine())
    val arr = IntArray(n){ token.nextToken().toInt() }

    var start = 0
    var end = 0
    var currentSum = 0
    var minLength = Int.MAX_VALUE

    while(true){
        when {
            // 현재 합이 S 보다 크거나 같은 경우 minLength, currentSum 을 조정하고 start 늘려주기
            currentSum >= s -> {
                minLength = kotlin.math.min(minLength, end - start)
                currentSum -= arr[start]
                start++
            }
            // currenSum 이 s 이상이 아니고 end 가 n 과 같다면 종료
            end == n -> break
            // currentSum 이 s 미만이므로 end 를 늘리면서 currentSum 합해주기.
            currentSum < s -> {
                currentSum += arr[end]
                end++
            }
        }
    }

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

후기

슬라이딩 윈도우라는 알고리즘 기법을 처음 알아서 혼자의 힘으로 풀지 못했다.
처음에는 풀이를 이상하게 어려웠을 뿐, 알고리즘 기법을 알고나서 다시 보니 꽤나 어렵지 않았다.

문제의 지문도 잘못읽어 연속된 수의 부분합이 아닌, 정렬 후 부분합을 구하려고 했는데 이러는 경우 NP 라는 문제가 되어 매우 어려운 문제로 변하게 된다고 한다.

언제나 말하지만, 문제의 지문을 잘 읽자.