[백준 20181] - 꿈틀꿈틀 호석 애벌레 효율성(Kotlin)[골드2]

문제

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

20181번: 꿈틀꿈틀 호석 애벌레 - 효율성

 

문제 풀이

문제를 읽어보니 누적합의 최댓값을 구하는 문제라고 생각을 했다.

DP 문제인줄 알았지만, 탐색하는 과정에서 시간이 오래 걸려서 투 포인터 알고리즘을 사용하기로 했다.

 

투 포인터 알고리즘을 사용했기 때문에 start와 end를 움직이면서 탐색을 진행한다.

기존의 투 포인터 문제들은 누적합을 넘어선 순간 start를 증가시키고, 누적합을 넘지 못한다면 end를 증가시킨다.

이와 같은 흐름은 동일하다.

해당 문제에서 추가된 부분은 DP값을 어떻게 업데이트 하느냐. 그것이 중요한 문제이다.

start가 의미하는것은 내가 여기서부터 먹었다.라고 이해를 하면 편할 것이고, end는 여기까지 먹었다를 의미한다고 생각하면 된다.

따라서 dp 값을 업데이트 하는 알고리즘은 누적합이 K를 넘기는 순간 비교를 한다.

start에서의 dp값과  + 먹은 값 - k , 자기 자신의 dp값을 비교한다.

자기 자신의 dp값을 비교하는 이유는 누적합이 k를 넘기지 못하는 경우 이전의 dp값을 계속해서 가져오기 때문이다.

 

9 6
1 5 4 4 2 3 10 3 5

 

예시를 들어서 설명하면

5를 먹은 순간 누적합이 6이 되고, 소화를 할 조건이 된다.

따라서 dp 값을 업데이트하는데 dp [1] = dp [0]+6-6 vs dp [0] -> dp [1]은 0이 된다.

먹은 순간 먹고 있는 먹이의 합에서 start가 가리키는 먹이의 값을 빼준다.

왜냐하면 탐색범위를 좁힐려고 start를 한 칸 증가시켜 줄 거 기 때문이다.

4를 먹은 순간, 소화를 할 조건이 된다.

dp[2] = dp [start-1]+9-6 vs dp [2] 

왜 start-1이냐는 당연하게도 start가 가리키는 먹이의 값은 dp를 구하는 과정에서 포함되어 있다. 

따라서 start-1의 dp값과 누적합을 더한 dp값으로 업데이트를 해줘야 한다.

 

말이 조금 어렵지만 start와 end를 이동시키면서 그곳에 해당하는 dp값과 먹은 먹이의 합을 비교해서 누적합을 갱신한다고 생각하면 편하다.

보통적으로 dp값을 깔끔하게 처리하기 위해서 dp 배열을 1부터 시작하는 방식을 많이 채용한다.

실제로 dp값을 이전의 값과 비교하는데 1부터 시작하면 dp[i-1]이 오류가 생기지 않기 때문이다.

하지만 나는 0부터 시작을 해서 코드적으로 많이 더럽고 if문이 많아서 조금 만족스럽지 않다..

따라서 코드를 보기보단 코드의 흐름을 보면 문제를 푸는데 도움이 많이 될 것 같다.

 

package TwoPointer.`20181_꿈틀꿈틀_호석_애벌레_효율성`.LJH

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

class `20181` {
    private var n = 0
    private var k = 0
    private lateinit var array: List<Long>
    private lateinit var dp: Array<Long>
    private val br = BufferedReader(InputStreamReader(System.`in`))

    fun run() {
        input()
        search()
        println(dp[n - 1])
    }

    private fun input() {
        val line = br.readLine().split(" ")
        n = line[0].toInt()
        k = line[1].toInt()
        array = br.readLine().split(" ").map { it.toLong() }
        dp = Array(n) { 0 }
    }

    private fun search() {
        var start = 0
        var end = 0
        var sum = 0L
        while (start <= end) {
            if (end > n)
                break
            if (sum >= k) { //누적합 뚫었을 경우
                if (start == 0) {
                    dp[end - 1] = max(dp[start] + sum - k, dp[end - 1])
                } else {
                    dp[end - 1] = max(dp[start - 1] + sum - k, dp[end - 1])
                }
                sum -= array[start]
                start++
            } else {
                if (end >= n)
                    break
                sum += array[end]
                if (end != 0)
                    dp[end] = max(dp[end], dp[end - 1])
                end++
            }
        }
    }
}

fun main() {
    `20181`().run()

}