[백준 알고리즘 #1806] 부분합

시작하며

부분합 또한 누적합과 비슷한점이 많다. 우선 누적합 배열을 구한 후, 해당 배열의 start포인터와 end포인터를 이동시켜가며 부분합을 구하는 것이다.

회고

부분합을 푸는데 있어, 2번의 반복문을 사용했더랬다. 하지만 이는 while 반복문 단 1개의 사용 및 start, end지점을 변경할 수 있다는 점을 생각하지 못한 점이다. 아래는 나의 첫 풀이이다.

fun main() {
    val (N, S) = readln().split(' ').map { it.toInt() }
    val sequences = readln().split(' ').map { if (it.toInt() >= S) { println(1); return } else it.toInt() }
    val accumeratedSequence = Array(N + 1) { 0 }
    var result = 0

    outterLoop@for (outterIndex in 1 until N + 1) {
        accumeratedSequence[outterIndex] = sequences[outterIndex - 1] + accumeratedSequence[outterIndex - 1]

        if (accumeratedSequence[outterIndex] >= S) {
            innerLoop@for (innerIndex in outterIndex downTo 0) {
                if (outterIndex == innerIndex || outterIndex == innerIndex + 1) continue@innerLoop

                if (result == outterIndex - innerIndex) break@innerLoop

                if (accumeratedSequence[outterIndex] - accumeratedSequence[innerIndex] >= S) {
                    result = outterIndex - innerIndex
                    break@innerLoop
                }
            }
        } else continue@outterLoop
    }
    println(result)
}

accumeratedSequence배열 사용 및 누적합을 구해주고 있다. 그리고 해당 누적합에 반복문을 돈다. 그리고 누적합들끼리의 뺄셈을 통해(=추가 반복문 사용) 부분합을 구하고 있는 모습이다.

하지만 이는 특정 구간에 있어 중복적으로 도는 문제가 발생한다. 예를 들어, accumeratedSequence에서 5번 인덱스 이전까지의 부분합을 모두 구한다 헀을 때, 아래와 같이 진행이 된다.
5 - 4 -> 5 - 3 -> 5 - 2 -> 5 - 1 -> 5 - 0

그 후, 로직이 진행되며 7번 인덱스 이전까지의 부분합을 모두 구한다 했을 때 아래와 같이 진행되는 문제가 있다.
7 - 6 -> 7 - 5 -> 7 - 4 -> 7 - 3 -> 7 - 2 -> 7 - 1 -> 7 - 0

7번 인덱스를 사용한 부분합 구하는 반복문 실행시, 0번 인덱스까지는 굳이 갈 필요가 없다. 이유는 5번 인덱스를 사용하며 부분합을 구하면서 이미 0번째까지 연산을 했었기 때문이다. 따라서 이런 경우, while문 사용 및 start, end포인터를 동적으로 바꿔가며 부분합을 구하는 방법이 있다. 아래는 이를 깨닫고 새로 작성한 코드이다.

풀이

fun main() {
    val (N, S) = readln().split(' ').map { it.toInt() }
    val sequences = readln().split(' ').map { if (it.toInt() >= S) { println(1); return } else it.toInt() }
    val accumeratedSequence = Array(N + 1) { 0 }
    var result = 100001

    for (index in 1 until N + 1) {
        accumeratedSequence[index] = sequences[index - 1] + accumeratedSequence[index - 1]
    }

    var start = 0
    var end = 1
    while (end <= N) {
        if (accumeratedSequence[end] - accumeratedSequence[start] >= S) {
            result = minOf(result, end - start)
            start++
        } else {
            end++
        }
    }

    println(if (result == 100001) 0 else result)
}

start, end 변수를 선언한다. 그 후, 반복문 조건에 따라 값을 바꿔준다. 이에 accumerateSequence배열 내, 어느 구간부터 어디까지를 반복해야할지를 알 수 있는 것이다.