백준 30460번: 스위치

문제: https://www.acmicpc.net/problem/30460

문제 풀이

DP

prev = 이전 시간까지의 스위치가 눌린 시간에 따른 최대 점수

cur = 현재 시간까지의 스위치가 눌린 시간에 따른 최대 점수

prev, cur를 각각 이전 시간, 현재 시간의 최대 점수로 나누고 각각 인덱스 0, 1, 2, 3에 대해 스위치가 눌리지 않은 상태, 스위치가 눌린 지 1초, 2초, 3초로 정의함

맨 처음에는 이전 시간에 스위치가 눌린지 1초, 2초, 3초가 불가능 하므로 언더플로우가 나지 않으면서 최댓값에 영향을 주지 않을만큼 작은 값 -2000으로 초기화함

그럼 현재 스위치가 눌리지 않은 상태려면 이전 상태는 눌리지 않은 상태거나 스위치가 눌린 지 3초가 되어 끝난 상태여야 하고 현재 점수 A는 그대로 들어감

현재 스위치를 누르려면 마찬가지로 이전 상태가 눌리지 않은 상태거나 스위치가 눌린 지 3초가 되어 끝난 상태여야 하고 현재 점수 A가 2배로 들어감

현재 스위치가 눌린 지 2초, 3초가 되려면 각각 이전 상태가 스위치가 눌린 지 1초, 2초가 되어야 하고 현재 점수 A가 2배로 들어감

N번 동안 위 규칙에 맞게 최댓값을 구하도록 점화식을 구현해 N초 이후의 최댓값을 구해 prev에 저장하고 이 배열내의 최댓값을 출력하면 정답

풀이 설명

$i$초에 $A_i$의 점수를 얻는 게임이 있다. $N$초 동안 진행하는 이 게임에서는 점수를 추가로 얻기 위해 $T$초에 스위치를 눌러 $T,T+1,T+2$초에 얻는 점수를 $2$배로 만들 수 있다. $T$초에 스위치를 누르면 $T+3$초부터 다시 스위치를 누를 수 있다.

게임이 진행되는 동안 스위치를 적절하게 눌렀을 때 얻을 수 있는 점수의 최댓값을 구해보자.

초마다 점수를 얻게 되므로 이전 시간까지 얻은 점수에 현재 시간의 점수를 더하는 구조이므로 특정 값을 이전 상태에서 더해 최댓값을 만드는 문제이기 때문에 이전 상태도 최댓값을 구해야 한다는 점에서 DP로 풀어야 한다는 점을 알 수 있다.

하지만 스위치가 눌린다면 현재 시간에 얻는 점수가 2배가 되고 스위치는 3초동안 지속되므로 현재 스위치가 몇초 동안 눌렸는지의 정보도 필요하다. 또한 스위치는 3초가 지나면 다시 누를 수 있기 때문에 스위치가 눌리지 않았을 때, 스위치가 눌린지 1초, 2초, 3초의 4가지 상태로 나뉠 수 있다.

문제를 풀기 위해 이전 상태의 스위치가 눌리지 않았을 때를 prev[0], 스위치가 눌린지 1초, 2초, 3초를 각각 prev[1], prev[2], prev[3]으로 정의하고, 현재 상태를 비슷하게 cur[0]부터 cur[3]까지라고 정의할 수 있다.

여기서 prev[1], prev[2], prev[3]을 초기화할 때 조심해야 하는 것은 첫 시작때에는 이미 스위치가 눌려있을 경우가 없기 때문에 prev[0]과 마찬가지로 0으로 놓으면 최댓값이 잘못 들어갈 수 있다는 점이다. 그러나 이 점수가 사용되지 않게 하도록 낮은 값을 잘못 놓게 된다면 N이 최대 20만이고 각 점수가 최저 -1000이므로 Int의 범위를 넘어서는 언더플로우가 날 수 있다. 따라서 점수로 들어올 수 있는 $A_i$의 최댓값이 1000이므로 이의 2배를 상쇄시킬 수 있는 -2000으로 초기화해야 한다는 점이다.

그러면 cur[0]은 현재 스위치가 눌리지 않은 것이므로 현재 점수 $A_i$를 그대로 더해주는데 이전 상태는 이전에도 스위치가 눌리지 않은 상태로 있던 prev[0]과 직전에 스위치의 3초가 끝난 prev[3]이 있을 수 있다. 따라서 cur[0]에는 prev[0]과 prev[3] 중 최댓값에다 $A_i$를 더한 값을 저장하면 된다.

cur[1]은 현재 스위치가 눌린지 1초인 상황인데 이는 지금 시각에 스위치를 눌렀다는 뜻이므로 직전에 스위치가 눌리지 않았거나 직전에 스위치가 끝났어야 누를 수 있기 때문에 prev[0]과 prev[3] 중 최댓값과 현재 점수 $A_i$를 2배한 값을 더한 값이 된다.

cur[2]는 현재 스위치가 눌린지 2초인 상황이므로 이미 직전에 스위치가 눌려있는 것이므로 prev[1]에 현재 점수 $A_i$를 2배한 값을 더한 값이 된다.

cur[3]은 cur[2]와 마찬가지로 직전 상황이 스위치가 눌린지 2초가 되야하므로 prev[2]에 현재 점수 $A_i$를 2배한 값을 더한 값이 된다.

그리고 한번 cur를 구했으면 다음 cur를 구할때는 현재 cur에 저장된 값이 이전 상태가 되는 것이므로 prev와 cur 배열을 서로 바꾸어서 다시 사용하면 된다. 이를 N번 하면 N초 진행했을 때의 각각 상황별 최대 점수가 prev 배열에 저장되어 있으므로 이 중 최댓값을 출력하면 정답이 된다.

소스 코드

import java.io.StreamTokenizer

fun main() = StreamTokenizer(System.`in`.bufferedReader()).run {
    fun nextInt(): Int{
        nextToken()
        return nval.toInt()
    }
    val N = nextInt()
    var prev = IntArray(4){-2000}
    prev[0] = 0
    var cur = IntArray(4)
    for(i in 0 until N){
        val A = nextInt()
        cur[0] = maxOf(prev[0], prev[3]) + A
        cur[1] = maxOf(prev[0], prev[3]) + A * 2
        cur[2] = prev[1] + A * 2
        cur[3] = prev[2] + A * 2
        prev = cur.also { cur = prev }
    }
    println(prev.max())
}