[백준 2208] - 보석 줍기(Kotlin)[골드2]

문제

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

2208번: 보석 줍기

 

문제 풀이

문제가 길지만, 문제의 핵심은 M개의 보석을 연속적으로 주워야 한다는 사실이다.

핵심을 지키면서 주울 수 있는 보석의 최대값을 구하는 전형적인 누적합 문제이다.

 

나는 i번째의 보석을 이동할 때의 누적합을 accumulateSum 이라는 1차 배열로 잡았다.

따라서 accumulateSum[4]라면 4번째의 보석까지 이동했을 때의 누적합이다. 

즉 여기는 1~4번째 보석의 가치 합이 들어가 있다.

 

이것을 왜 구해야 하는지 생각을 해보자.

우리가 구하고자 하는 보석 최대의 가치 합이란 어떻게 보면 구간을 말한다.

i~ j까지 보석을 주웠을 때의 합이 최대가 되는 구간이다. 물론  j-i는 M이상이어야 할 것이다.

 

그러면 i~j까지의 구간합은 어떻게 구하는가?

이 구간합을 구하기 위해서 우리는 accumulateSum이라는 배열을 계산한 것이다.

즉 i~j까지의 구간합은 accumulateSum [j] - accumulateSum [i]가 될 것이다.

 

그렇다면 dp배열에 대한 점화식을 세워보자.

dp [i] : i번째의 보석까지 이동했을 경우 누적합의 최댓값이다.

식은 다음과 같다.

dp [i] = max(dp [i-1] + 보석[i] , accumulateSum [i]- accumulateSum [i-m])
즉 이전의 구간에서 보석을 추가로 담는 경우와 새로운 구간, 즉 이전까지의 선택을 무시하고 i-m ~ i까지의 보석합을 의미한다.

 

 

전체 코드

import kotlin.math.*

class Solution {
    private val br = System.`in`.bufferedReader()
    private lateinit var items: IntArray
    private lateinit var accumulateSum: IntArray
    private lateinit var dp: IntArray
    private var n = 0
    private var m = 0
    private var answer = 0

    init {
        input()
        calculateMaxValue()
        print(answer)
    }

    private fun input() {
        val line = br.readLine().split(" ")
        n = line[0].toInt()
        m = line[1].toInt()
        items = IntArray(n + 1)
        accumulateSum = IntArray(n + 1)
        dp = IntArray(n + 1)
        for (i in 1..n) {
            items[i] = br.readLine().toInt()
            accumulateSum[i] = accumulateSum[i - 1] + items[i]
        }
        dp[m] = accumulateSum[m]
    }

    private fun calculateMaxValue() {
        for (i in m + 1..n) {
            dp[i] = max(dp[i - 1] + items[i], accumulateSum[i] - accumulateSum[i - m])
            answer = max(answer, dp[i])
        }
    }
}

fun main() {
    val solution = Solution()
}