백준 19951번
https://www.acmicpc.net/problem/19951

문제

---

생각하기

---

• 누적 합 알고리즘을 적용하여 최적화를 통해 풀 수 있는 문제이다.

  • 구간 마킹을 통해서 미리 표시를 해두고 최종적으로 합산을 한다.

동작

누적 합을 적용하기 전에 미리 k의 값들을 구간 시작과 끝의 기점에 마킹을 해둔다.

    val prefixSums = IntArray(N + 2)
    for (i in 0 until M) {
        StringTokenizer(br.readLine()).run {
            val a = nextToken().toInt()
            val b = nextToken().toInt()
            val k = nextToken().toInt()
            // 구간 마킹하기
            prefixSums[a] += k
            prefixSums[b + 1] -= k
        }
    }

시작점인 prefixSums[a] 에는 +k를 해두고 끝점인 prefixSums[b + 1]에는 -k를 통해서 시작과 끝을 마킹해둔다.

이때 시작점은 [a]로 시작하면서 끝점은 [b + 1]로 지정되는 이유는
[b]까지는 k 값의 영향을 받아야 하지만 그 다음인 [b + 1] 부터는 누적합에서도 k의 이전 영향을 제거하기 위해 [b + 1]은 음수를 더해서 마킹하도록 한다.

결과

코드

---

Kotlin

import java.io.*
import java.util.*

// input
private lateinit var br: BufferedReader

// variables
private var N = 0
private var M = 0

fun main() {
    br = BufferedReader(InputStreamReader(System.`in`))
    val bw = BufferedWriter(OutputStreamWriter(System.out))

    input()

    bw.write(solve())
    bw.close()
} // End of main

private fun solve(): String {
    val sb = StringBuilder()

    val heights = IntArray(N + 1)
    StringTokenizer(br.readLine()).run {
        for (i in 1..N) {
            heights[i] = nextToken().toInt()
        }
    }

    val prefixSums = IntArray(N + 2)
    for (i in 0 until M) {
        StringTokenizer(br.readLine()).run {
            val a = nextToken().toInt()
            val b = nextToken().toInt()
            val k = nextToken().toInt()
            // 구간 마킹하기
            prefixSums[a] += k
            prefixSums[b + 1] -= k
        }
    }

    // 마킹 부분 누적합 구하기
    for (i in 0..N) {
        prefixSums[i + 1] += prefixSums[i]
    }

    for (i in 1..N) {
        heights[i] += prefixSums[i]
        sb.append(heights[i]).append(' ')
    }

    return sb.toString()
} // End of solve()

private fun input() {
    StringTokenizer(br.readLine()).run {
        N = nextToken().toInt()
        M = nextToken().toInt()
    }
} // End of input()