백준 9465번: 스티커

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

문제 풀이

DP

arr[i][j] = i행 j열의 스티커의 점수

dp[i][j] = i행 j열의 스티커를 떼었을 때의 스티커 점수의 최대 합

i가 0으로 시작하는 행의 인덱스인 0과 1이므로 1과 xor 연산을하면 항상 반대 행의 인덱스가 나오게 되므로 점화식은 다음과 같음

dp[i][j] = arr[i][j] + max(dp[1 xor i][j - 2], dp[1 xor i][j - 1])

점화식에 따라 dp 테이블을 구하고 마지막 열의 두 값을 비교해 더 큰 값을 출력하면 정답

풀이 설명

스티커 2n개를 구매했다. 스티커는 2행 n열로 배치되어 있다. 스티커의 품질은 매우 좋지 않다. 스티커 한 장을 떼면, 그 스티커와 변을 공유하는 스티커는 모두 찢어져서 사용할 수 없게 된다. 즉, 뗀 스티커의 왼쪽, 오른쪽, 위, 아래에 있는 스티커는 사용할 수 없게 된다.

각 스티커에 점수를 매기고, 점수의 합이 최대가 되게 스티커를 떼어내려고 한다. 뗄 수 있는 스티커의 점수의 최댓값을 구하는 프로그램을 작성하시오. 즉, 2n개의 스티커 중에서 점수의 합이 최대가 되면서 서로 변을 공유 하지 않는 스티커 집합을 구해야 한다.

스티커를 열마다 생각해보면 다음과 같이 생각할 수 있다. 만약 이전 열에서 1행에서의 스티커를 떼어냈다면 현재 열에서는 2행에서의 스티커를 떼어낼 수 있을 것이다. 즉, 이전 열에서 스티커를 떼어냈다면 현재 열에서는 다른 행에서의 스티커를 떼어낼 수 있다는 뜻이다.

하지만 예시에서도 나오듯이 모든 열에서 항상 스티커를 떼어내지 않아도 된다. 현재 열을 j 열이라고 하면 j - 1 열에서 스티커를 떼지 않는다고 생각하면 j - 2 열에서는 스티커를 뗀다는 소리다. 여기서 생각해야 하는 것은 만약 j - 2열에서 1행의 스티커를 떼었는데 현재 행에서도 1행의 스티커를 뗀다면 아래 표처럼 j - 1열의 2행의 스티커는 뗄 수 있는 조건이라는 것이다.

	j - 2 열	j - 1 열	j 열
1행	O	X	O
2행	X	O	X

따라서 이전 열의 스티커를 떼지 않는 경우는 전전열의 다른 행의 스티커를 떼어야 한다는 것이므로 이에 따라 점화식을 세워서 DP 테이블을 채운 후에 마지막 열의 값을 비교하면 된다.

항상 마지막 열의 스티커를 떼는 이유는 만약 마지막 이전 열의 스티커를 떼지 않았다면 마지막 열의 스티커를 떼는 것이 합이 더 커지는 것이고, 마지막 이전 열의 스티커를 떼었더라도 마지막 열의 다른 행의 스티커를 떼는 것이 합이 더 커지는 것이기 때문이다.

따라서 DP 테이블에서 마지막 열의 두 행의 값을 비교해 더 큰 값을 출력해주면 정답이 된다.

소스 코드

import java.io.StreamTokenizer

fun main() = StreamTokenizer(System.`in`.bufferedReader()).run {
    fun nextInt(): Int{
        nextToken()
        return nval.toInt()
    }
    val T = nextInt()
    val bw = System.out.bufferedWriter()
    repeat(T){
        val n = nextInt()
        val arr = Array(2){IntArray(n)}
        for(i in 0 until 2){
            for(j in 0 until n){
                arr[i][j] = nextInt()
            }
        }
        val dp = Array(2){IntArray(n)}
        dp[0][0] = arr[0][0]
        dp[1][0] = arr[1][0]
        if(n > 1){
            dp[0][1] = dp[1][0] + arr[0][1]
            dp[1][1] = dp[0][0] + arr[1][1]
        }
        for(j in 2 until n){
            for(i in 0 until 2){
                dp[i][j] = arr[i][j] + maxOf(dp[1 xor i][j - 2], dp[1 xor i][j - 1])
            }
        }
        bw.append("${maxOf(dp[0][n - 1], dp[1][n - 1])}\n")
    }
    bw.flush()
    bw.close()
}