[Kotlin] 백준 27450 : 플래그 대사 좀 그만 말해요

문제 링크

27450번: 플래그 대사 그만 좀 말해요

---

문제 해설

가장 기본적인 풀이 방법은 한별이가 각 위치에서 "해치웠나?"를 외칠때마다 외침의 영향을 받는 부하들의 강함을 증가시켜 주는 것이다. 하지만 \(N\)과 \(K\)가 각각 최대 50만이기 때문에 이 방법을 사용하면 각 위치에서 1번의 연산만 수행하더라도 1250억번의 연산을 수행하게 되어 시간 초과가 발생한다.

 

이 문제를 좀 더 효율적으로 해결하기 위해서는 누적 합을 응용하는 방법을 사용할 수 있다. 어떤 지점 \(p\)에서 \(i\)만큼 떨어진 \(p_i\)에 있는 부하가 \(p\)에서 한별이가 한 번 외친 대사를 듣고 강해지는 힘은 \(\max (0,K-i)\)가 된다. 한별이는 각 위치에서 한별이는 \(x_p\)번 대사를 외칠 것이기 때문에 \(p_i\)에 있는 부하가 \(p\)에서 한별이가 외친 대사를 듣고 강해지는 힘은 \(x_p\max (0,K-i)\)가 된다. 즉, 각 위치의 부하가 이전 위치에서 한별이의 외침 소리를 듣고 강해지는 힘은 현재 위치와 이전 위치 사이의 거리에 \(x_p\)를 곱한 수치가 된다.

 

이를 활용하면 각 위치에서 필요한 한별이의 외침 횟수를 구하면서 바로 직전 위치에서 증가한 힘을 토대로 현재 위치의 부하가 이전 위치들에서 한별이가 외친 대사들로 강화된 힘을 구할 수 있다. 즉, (현재 위치에서 대사를 외치지 않고 강화된 힘) = (직전 위치에서 강화된 힘) - (현재 위치까지 영향을 주는 외침 횟수)가 된다.

 

마지막으로 현재 위치까지 영향을 주는 외침 횟수를 구하기 위해 덱을 사용할 수 있다. 현재 위치에서 대사를 외칠 때 유효 외침 횟수를 현재 위치에서 대사를 외친 횟수를 증가시키고, 덱에 현재 위치의 외침 횟수를 추가한다. 그리고, 덱의 가장 앞에 있는 외침 횟수를 제거하면서 유효 외침 횟수에서 차감한다.

 

이를 통해 \(O(n)\)의 시간복잡도로 문제를 풀 수 있다.

Code

import java.util.StringTokenizer

fun main() = with(System.`in`.bufferedReader()) {
    val (n, k) = readLine().split(' ').map { it.toInt() }
    val p = IntArray(1) + StringTokenizer(readLine()).run { IntArray(n) { nextToken().toInt() } }
    val t = IntArray(1) + StringTokenizer(readLine()).run { IntArray(n) { nextToken().toInt() } }
    val additionalPower = IntArray(n + 1)
    val speech = ArrayDeque<Int>().apply { repeat(k) { add(0) } }
    var effectiveShout = 0
    var shout = 0L
    for (i in 1..n) {
        additionalPower[i] = additionalPower[i - 1] - effectiveShout
        p[i] += additionalPower[i]
        val count = if (t[i] <= p[i]) 0 else (t[i] - p[i]) / k + if ((t[i] - p[i]) % k == 0) 0 else 1
        shout += count
        effectiveShout += count
        speech.add(count)
        additionalPower[i] += (count * k).also { p[i] += it }
        effectiveShout -= speech.removeFirst()
    }
    println(shout)
}