[백준] 11659 (구간 합 구하기 4)

#1 알고리즘

#1-1 동적 프로그래밍

동적 프로그래밍 (Dynamic Programming), 상향식(Bottom-up) 및 하향식(Top-down) 접근

상향식 동적 프로그래밍 문제다.

 

#1-2 구간 합 도출 방법

캐싱을 위해 모든 range 예를 들어, 1..300, 40..70, 998..999, ...들을 전부 구하는 것은 사실상 불가능하다. 무수한 경우의 수가 있기에 저장 공간과 계산 시간 모두 안드로메다로 날아가 버린다.

 

대신, 1..1, 1..2, 1..3, 1..4, ... 을 보유하는 캐시용 배열 하나(이하 cacheArray)를 선언한다. 이러면 cacheArray 하나만으로 쉽게 특정 구간의 합을 구할 수 있다. 가령 range가 3..5라면 1..5까지의 합에서 1..3까지의 합을 뺀다. 이러면 4..5까지의 합이 나온다. 여기에 3을 더하면, 처음 range인 3..5까지의 합이 나온다. 이를 코드로 표현하면 아래와 같다.

 

lateinit var numbers: Array<Int>
lateinit var sums: Array<Int>

fun calculateRangeSum(range: IntRange): Int {
    return sums[range.last] - sums[range.first] + numbers[range.first]
}

 

#1-3 인덱싱 주의

배열의 길이(length)와 원소의 순번(index)

문제의 조건은 1-based indexing을 사용한다. 이 점에 주의한다.

 

#2 코드 - 코틀린

var n = -1
var m = -1
lateinit var numbers: Array<Int>
lateinit var sums: Array<Int> // (예) 1부터 7까지의 합은 sum[7]에 담김

fun main() {
    val nAndM = readln().split(" ")
    n = nAndM[0].toInt()
    m = nAndM[1].toInt()

    numbers = Array(n + 1) { -1 } // 문제에서 Input되는 수의 범위가 1-based indexing 기반이므로 n이 아니라 n + 1
    val numberStrings = readln().split(" ") // 0-based indexing
    for (i: Int in 1..n) {
        numbers[i] = numberStrings[i - 1].toInt()
    }

    sums = Array(n + 1) { -1 }
    sums[1] = numbers[1]
    for (i: Int in 2..n) {
        sums[i] = sums[i - 1] + numbers[i]
    }

    val ranges = Array(m) { -1..-1 }
    for (i: Int in 0..<m) {
        val rangeStrings = readln().split(" ")
        ranges[i] = rangeStrings[0].toInt()..rangeStrings[1].toInt()
    }

    for (range in ranges) {
        println(calculateRangeSum(range))
    }
}

fun calculateRangeSum(range: IntRange): Int {
    /* [가령 range가 3..5라면]
     * 1..5까지의 합에서 1..3까지의 합을 빼면
     * 4..5까지의 합이 나옴
     * 여기에 3을 더하면, range인 3..5까지의 합이 나옴
     */
    return sums[range.last] - sums[range.first] + numbers[range.first]
}