백준 - 스티커(Kotlin)

본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다.

https://github.com/ROUTINE-STUDY/Algorithm

 

저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다.

GitHub - ROUTINE-STUDY/Algorithm: 초보 알고리즘 스터디 / 누구나 참여 가능

문의는 댓글 바람.

 

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

 

[문제 설명]

스티커를 선택해서 가장 최고 점수를 만들어라.

[접근 방법]

사방면이라는 점에 집중해서는 안된다.

이럴 땐, n = 1인 경우부터 차례대로 규칙을 찾으면 정답을 알 수 있다.

n = 1인 모든 경우

n = 1일 때 선택할 수 있는 스티커의 방법은 위와 같다.

왜 색칠하지 않는 경우의 수도 따지냐고 물을 수 있다.

만약, 모든 열에서 하나를 무조건 선택한다면 지그재그형으로 밖에 스티커를 고를 수 없게 된다.

n = 3일 때

위에 두 방법은 스티커의 개수를 최대한으로 뽑을 수 있지만, 그 합이 최댓값이라는 보장은 할 수 없다.

우리는 스티커의 개수를 최대로 뽑는 게 아닌, 최대한 점수를 내야 한다.

스티커를 중간에 한 번 뽑지 않은 게 최댓값

그렇다면 이걸 어떻게 구할까?

이번에 위에 스티커를 고를 경우.

이전 스티커의 아래 점수와 위에 스티커의 점수의 합을 구한다.

이전 스티커를 뽑지 않은 경우와 위에 스티커를 뽑은 경우의 합을 구한다.

둘 중에 큰 값이 위에 스티커를 골랐을 때 나올 수 있는 최댓값이다.

시간복잡도는 O(t * n)

 

[내 답안 수정하기]

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import java.util.StringTokenizer

fun main() = with(BufferedReader(InputStreamReader(System.`in`))){
    val bw = BufferedWriter(OutputStreamWriter(System.out))
    // 테스트 케이스 경우의 수
    val t = readLine().toInt()
    repeat(t) {
        // 스티커 한 층의 개수
        val n = readLine().toInt()
        // 각 2행 n열 박스에 스티커의 점수를 담는 배열
        val array = Array(2) { IntArray(n) }
        val dp = Array(3) { IntArray(n) }
        repeat(2) { row ->
            val st = StringTokenizer(readLine())
            for (col in 0 until n) {
                array[row][col] = st.nextToken().toInt()
            }
        }

        // 초기화 :
        // 위에 색칠한 경우
        dp[0][0] = array[0][0]
        // 아래 색칠한 경우
        dp[1][0] = array[1][0]
        for (i in 1 until n) {
            // 이번에 위를 색칠하는 경우 = max(이전에 아래 색칠한 경우 + 위에 색칠, 이전에 색칠 안함 + 위에 색칠)
            dp[0][i] = dp[1][i - 1].coerceAtLeast(dp[2][i - 1]).plus(array[0][i])
            // 이번에 아래를 색칠하는 경우 = max(이전에 위를 색칠한 경우 + 아래를 색칠, 이전에 색칠 안함 + 아래를 색칠)
            dp[1][i] = dp[0][i - 1].coerceAtLeast(dp[2][i - 1]).plus(array[1][i])
            // 이번에 색칠을 안하는 경우 = max(이전에 위를 색칠, 이전에 아래를 색칠)
            dp[2][i] = dp[0][i - 1].coerceAtLeast(dp[1][i - 1])
        }
        bw.write("${dp[0][n - 1].coerceAtLeast(dp[1][n - 1]).coerceAtLeast(dp[2][n - 1])}\n")
    }
    bw.flush()
}