[백준][Kotlin] - 스위치(30460)

문제 소개

🥇️ 문제 레벨 : 골드5
🔔 문제 유형 : 다이나믹 프로그래밍
💬 풀이 언어 : Kotlin
🖇️ 문제 링크 : 백준 문제 링크

📝 문제

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

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

🤔 문제 분석

DP를 사용하는 문제기 때문에, 점화식을 먼저 구해야 한다. 우선 문제에 나와있듯이, 스위치를 누르는 선택지와 누르지 않는 선택지가 존재한다. 이 때, 맨 앞에서부터 접근할 경우, 이전에 버튼을 눌렀는지에 대한 여부를 판단해야하기 때문에 복잡해질 수 있다. 때문에 뒤에서부터 접근을 해봤다.

점화식

우선, dp[i]는 i초부터 게임이 끝날 때까지 얻을 수 있는 최대 점수를 의미한다. 즉, 풀이 코드는 뒤부터 접근을 하기 때문에 dp[0]이 정답이 되는 것이다.

i초에서 가능한 선택지는 두 가지 뿐이다.

스위치를 누르지 않는 경우

• i초의 점수 scores[i]를 그대로 얻는다.
• 다음 상태 : dp[i + 1]

스위치를 누른 경우

• i, i + 1, i + 2초 점수 2배 이벤트
• 다음 상태 : dp[i + 3]

즉, 정리하면 다음과 같을 것이다.

dp[i] = max(
    dp[i + 1] + scores[i],
    dp[i + 3] + 2 * (scores[i] + scores[i + 1] + scores[i + 2])
)

이제, 이를 n - 1에서 0까지 역순으로 계산하면 정답을 얻을 수 있다.

for (i in n - 1 downTo 0) {  
    dp[i] = max(
        dp[i + 1] + scores[i],
        dp[i + 3] + 2 * (scores[i] + scores[i + 1] + scores[i + 2])
    )  
}

시뮬레이션

다음 예제를 통해 시뮬레이션을 돌려보자.

5
-1 -2 -3 4 5

dp = [0, 0, 0, 0, 0, 0, 0, 0]
scores = [-1, -2, -3, 4, 5, 0, 0, 0]

• i = 4
  • dp[5] + scores[4]
    • = 0 + 5 → 5
  • dp[7] + (scores[4] + scores[5] + scores[6]) * 2)
    • = 0 + 2 * (5 + 0 + 0) → 10
  • dp = [0, 0, 0, 0, 10, 0, 0, 0]
• i = 3
  • dp[4] + scores[3]
    • = 10 + 4 → 14
  • dp[6] + (scores[3] + scores[4] + scores[5]) * 2)
    • = 0 + 2 * (4 + 5 + 0) → 18
  • dp = [0, 0, 0, 18, 10, 0, 0, 0]
• i = 2
  • dp[3] + scores[2]
    • = 18 + -3 → 15
  • dp[5] + (scores[2] + scores[3] + scores[4]) * 2)
    • = 0 + 2 * (-3 + 4 + 5) → 12
  • dp = [0, 0, 15, 18, 10, 0, 0, 0]
• i = 1
  • dp[2] + scores[1]
    • = 15 + -2 → 13
  • dp[4] + (scores[1] + scores[2] + scores[3]) * 2)
    • = 10 + 2 * (-2 + -3 + 4) → 8
  • dp = [0, 13, 15, 18, 10, 0, 0, 0]
• i = 0
  • dp[1] + scores[0]
    • = 13 + -1 → 12
  • dp[3] + (scores[0] + scores[1] + scores[2]) * 2)
    • = 18 + 2 * (-1 + -2 + -3) → 6
  • dp = [12, 13, 15, 18, 10, 0, 0, 0]

정답 : 12

😎 최종 코드

메모리 : 36152 KB
시간 : 300 ms

import java.util.StringTokenizer  
import kotlin.math.max  

fun main() = with(System.`in`.bufferedReader()) {  
    val n = readLine().toInt()  

    val st = StringTokenizer(readLine())  
    val scores = IntArray(n + 3) { 0 }  
    repeat(n) {  
        datum[it] = st.nextToken().toInt()  
    }  

    val dp = Array(n + 3) { 0 }  

    for (i in n - 1 downTo 0) {  
        dp[i] = max(
            (dp[i + 1] + scores[i]), 
            (dp[i + 3] + (scores[i] + scores[i + 1] + scores[i + 2]) * 2)
        )  
    }  

    println(dp[0])  
}