백준 9465 스티커

https://www.acmicpc.net/problem/9465

스티커 판에서 점수 합이 최대가 되도록 스티커를 떼어내고, 그 때의 최댓값을 출력하는 문제이다.

스티커는 뜯으면 상하좌우의 스티커들은 손상되어 점수를 얻을 수 없다.

스티커의 개수가 최대 200,000 개이므로 직접 하나씩 떼어 보는 방법은 시간초과가 날 것 같다고 생각했다.

판의 높이가 2로 고정이고 한 스티커를 떼면 상하좌우 스티커들이 소모된다는 점을 생각해 판의 길이를 늘리며 왼쪽부터 스티커를 떼어 보기로 하였다.

n이 1인 경우 위쪽 스티커와 아래쪽 스티커의 점수 중 큰 값이 정답이다.

n이 2인 경우 왼쪽 위 + 오른쪽 아래 vs 왼쪽 아래 + 오른쪽 위 값 중 큰 것이 정답이다.

1	3
4	5

1과 5를 뜯는 경우 vs 3과 4를 뜯는 경우를 비교한다.

그럼 n이 3 이상인 경우는??

50	10	100	20	40
30	50	70	10	60

단순히 지그재그로 더한 값을 비교하면 안 되는 것을 제공된 예시에서 확인할 수 있다. 기울어진 값들을 더한 값이 최대이다.

이 문제를 풀기 위해 다이나믹 프로그래밍 방법을 생각하였다.

n이 1과 2인 경우는 정답을 구하는 방법이 고정이므로 이를 기반으로 n을 확장하기로 하였다.

스티커 판과 똑같은 크기의 dp 배열(2 x n)을 선언하여 [0][i]에는 i번째 줄의 위쪽 스티커를 마지막으로 떼어내는 경우의 최대 합으로 정의하였다.

50	40	0	0	0
30	100	0	0	0

먼저 n이 1과 2인 경우를 개별로 처리하고, 3 이상인 경우 dp 배열을 생성한다.

두번째 줄의 값이 40, 100인것은 [1][0]의 값인 30에 현재 위치를 마지막으로 뜯어 낸 10의 값을 더한 것이고 (40), [0][0]의 값에 50의 값을 더한 것이다(100).

그럼 노란 위치의 값을 구해보자.

노란 위치는 원래 스티커 판의 [0][2]위치에 있는 100을 마지막으로 떼어 낼 때의 최댓값에 해당한다.

칸의 값을 구하려면 두 칸 전의 반대 위치 값(30) + 현재 값(100) vs 전 칸의 반대 위치 값(100) + 현재 값(100), 두 값중 큰 값을 선택하면 된다.

두 칸 전의 위치의 값을 구하는 이유는 예제와 같이 바로 이전 칸을 선택하지 않는 경우에 대비하기 위해서이다.

그리고 두 칸 전의 '반대 위치'의 값에 더하는 이유는?

두 칸 전의 같은 위치를 선택한 경우에는 바로 이전 칸의 반대 위치를 선택할 수 있다는 것이고, 이전 칸을 선택하는 경우의 결과값이 무조건 더 크기 때문이다. 또한 이것은 이미 고려된 값이다.

세 칸 전은 고려하지 않아도 좋은가?

내가 생각한 답은 Yes이다.

세 칸 전을 선택하고 현재 칸을 선택한다는 것은 이전 두 칸을 선택하지 않고 버린다는 뜻이다.

위 예시에서 볼 수 있듯이 세 칸 전을 선택하고 현재 칸을 선택하는 경우 이전 두 칸 중 하나를 선택해도 문제가 없는 경우가 반드시 존재하며, 스티커의 점수 값이 양수인 이상 꼭 선택해야 최댓값이 등장한다.

따라서 세 칸 전은 고려할 필요가 없다.

정리된 내용에 따라 점화식을 만들어 보자.

dp배열의 i가 0과 1인 경우는 미리 입력해 두고
$dp[0][i] = max(dp[1][i - 2] + input[0][i], dp[1][i - 1] + input[0][i])$
$dp[1][i] = max(dp[0][i - 2] + input[1][i], dp[0][i - 1] + input[1][i])$
가 된다.

이를 모두 구한 뒤, dp 배열의 맨 오른쪽 끝 값들인 dp[0][n - 1]과 dp[1][n - 1]중에 큰 값을 출력한다.

import kotlin.math.max

fun main(args: Array<String>): Unit = with(System.`in`.bufferedReader()) {
    val T = readLine().toInt()
    val answer = StringBuilder()

    for(case in 1..T){
        val n = readLine().toInt()

        val line1 = readLine().split(' ').map{it.toInt()}
        val line2 = readLine().split(' ').map{it.toInt()}

        val dp = arrayOf(
            IntArray(n){0},
            IntArray(n){0}
        )

        if(n == 1){
            answer.append("${max(line1[0], line2[0])}\n")
            continue
        }else if(n == 2){
            answer.append("${max(line1[0] + line2[1], line1[1] + line2[0])}\n")
            continue
        }

        dp[0][0] = line1[0]
        dp[1][0] = line2[0]
        dp[0][1] = line2[0] + line1[1]
        dp[1][1] = line1[0] + line2[1]

        for(i in 2 until n){
            dp[0][i] = max(dp[1][i - 2] + line1[i], dp[1][i - 1] + line1[i])
            dp[1][i] = max(dp[0][i - 2] + line2[i], dp[0][i - 1] + line2[i])
        }

        answer.append("${max(dp[0][n - 1], dp[1][n - 1])}\n")
    }

    print(answer.toString())
}