[ 백준 9465] 스티커 (Kotlin 풀이)

1.문제 

상근이의 여동생 상냥이는 문방구에서 스티커 2n개를 구매했다. 스티커는 그림 (a)와 같이 2행 n열로 배치되어 있다. 상냥이는 스티커를 이용해 책상을 꾸미려고 한다.

상냥이가 구매한 스티커의 품질은 매우 좋지 않다. 스티커 한 장을 떼면, 그 스티커와 변을 공유하는 스티커는 모두 찢어져서 사용할 수 없게 된다. 즉, 뗀 스티커의 왼쪽, 오른쪽, 위, 아래에 있는 스티커는 사용할 수 없게 된다.

2. 입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 점수이다. 연속하는 두 정수 사이에는 빈 칸이 하나 있다. 점수는 0보다 크거나 같고, 100보다 작거나 같은 정수이다. 

3. 출력

각 테스트 케이스 마다, 2n개의 스티커 중에서 두 변을 공유하지 않는 스티커 점수의 최댓값을 출력한다.

---

4. 포인트

1. 동적계획법을 이용해 푼다.
2. 점화식을 세울 수 있어야한다 

   1. dp[1][i] = arr[1][i] + max(dp[0][i - 2], dp[0][i - 1])

   2. dp[0][i] = arr[0][i] + max(dp[1][i - 2], dp[1][i - 1])

3. 파악이 어렵다면 흐름을 역으로 생각해보자 (현재 위치의 수가 어떤 조건으로 만들어질 수 있는지 생각해보기- TopDown식으로 사고해보기)

1.  

4. 문제 풀이

다양한 경우의 수가 머릿속에 떠 다녔고 규칙을 찾을 수 없었다. 혼자 힘으로 풀지못하고 답을 참고하여 풀 수 있었다.

 

DP 문제의 점화식이 정리 되지 않을 때는 Top-Down 방식으로 사고하여 현재 위치의 값이 어떤 과정을 통해 만들어질 수 있는지를 생각해보는 것이 많이 도움이된다. 

 

각 스티커 자리별 최대값을 담은 배열 dp[][] 에 대해서 생각해보자

dp[0][i] 의 값은  dp[1][i-1](기존 스티커 값을 담은 배열)  혹은 dp[1][i-2] 를 통해서만 접근 될 수 있다.

arr[1][i-3] 부터는 arr[1][i-1] 과 arr[1][i-2] 를 거쳐서 갈 수 있기 때문이다.

이를 고려해 위와 같은 점화식을 얻을 수 있다.

 

또한 경계값에 대한 추가적인 처리가 필요하다. i-1 과 i-2 로 접근하기때눔에 열값이 1인 경우를 넣어주고 시작해야한다.

 

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*
import kotlin.math.max

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val T = readLine().toInt()

// 해당위치까지 올 수 있는 값들을 누적하여 해당 위의 값을 결정한다.
    repeat(T) {

        val N = readLine().toInt()
        val arr = Array<Array<Int>>(2) { Array<Int>(N + 1) { 0 } }
        val dp = Array<Array<Int>>(2) { Array<Int>(N + 1) { 0 } }

        for (i in 0..1) {
            var st = StringTokenizer(readLine(), " ")
            for (j in 1..N) {
                arr[i][j] = st.nextToken().toInt()
            }
        }

        if (N >= 1) {
            dp[0][1] = arr[0][1]
            dp[1][1] = arr[1][1]
        }

        for (i in 2..N) {
            dp[0][i] = arr[0][i] + max(dp[1][i - 2], dp[1][i - 1])
            dp[1][i] = arr[1][i] + max(dp[0][i - 2], dp[0][i - 1])
        }

        println(max(dp[0][N], dp[1][N]))
    }


}