백준 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]
은 음수를 더해서 마킹하도록 한다.
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()