[백준 알고리즘 #2003] 수들의 합2

시작하며

해당 문제는 이전에 포스팅했던 부분합과 굉장히 유사하다.

1. 누적합 배열 생성
2. 누적합 배열을 가리킬 start, end포인터 선언
3. 누적합 배열 반복문 돌리며, start와 end포인터를 적절히 이동시킴
4. 이동하는 와중, 값이 목표로 헀던 값(=M)과 동일할시, 프로퍼티의 값을 1 증가시킴

풀이

부분합을 이미 풀어봤다면 아주 간단히 풀 수 있는 문제이다. 아래 코드를 보면 알겠지만, 이전에 풀었던 부분합과 매우 유사하다는걸 알 수 있다.

fun main() {
    val (n, m) = readln().split(' ').map { it.toInt() }
    val sequences = readln().split(' ').map { it.toInt() }
    var result = 0

    val accumeratedSequences = Array(n + 1) { 0 }
    for (index in 1 until n + 1) {
        accumeratedSequences[index] = sequences[index - 1] + accumeratedSequences[index - 1]
    }

    var start = 0
    var end = 1

    while (end < n + 1) {
        if (accumeratedSequences[end] - accumeratedSequences[start] < m) {
            end++
        } else if (accumeratedSequences[end] - accumeratedSequences[start] == m) {
            result++
            end++
        } else {
            start++
        }
    }

    println(result)
}