백준 1912번: 연속합 (Kotlin)

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

1912번: 연속합

 

풀이

어떤 방법을 써야 할까?

1 <= n <= 100,000이므로 모든 경우를 탐색해보면 시간초과가 나고, 정렬을 해서 푸는 문제도 아닌 듯 하다. 따라서, 이분 탐색을 사용하는 문제는 아니고, 그리디한 방법도 떠오르진 않는다.

접근 방법에 대해 생각해봤는데, 사실 이 문제는 다이나믹 프로그래밍을 사용하는 것으로 유명한 문제 중 하나이다.

 

나는 다이나믹 프로그래밍 문제를 다음과 같은 절차로 풀려고 한다.

 

1. 반복문에서 사용할 점화식을 찾기 위해 함수를 정의한다. 

-> dp[i]: 배열이 i번째 까지만 있을 때, 시작 위치가 어디든 number[i]로 끝나는 최대 연속합 (number[?] ~ number[i])

ex) 2, 1, -4, 3, 4, -4, 6, 5, -5, 1 -> dp[2] = -1, dp[3] = 3

2. 문제에 따라서 아무것도 없는 상태(ex: 0) or 첫 인덱스의 값을 초기 값으로 설정한다.

-> dp[0] = number[0]

3. (2.)를 고려해서, 모든 경우의 수를 커버할 수 있는 점화식을 찾는다. 

-> dp[i] = {

                if (dp[i-1] < 0) number[i] 

                else) dp[i-1] + number[i]

              }

             < == > max( dp[i - 1] + number[i] , number[i] ) 

(수학적 귀납법과 같다!)

 

음수가 키포인트이지만, number[i]가 아니라 dp[i-1]이 음수인지의 여부가 중요하다. number[i]가 음수일지라도 dp[i-1]이 양수이면 dp[i] = dp[i-1] + number[i]이어야 한다. 그래야 1, -4, 3, 4, -4, 6, 5, -5, 1에서 3, 4, -4, 6, 5를 찾아낼 수 있다. 반면에 number[i]가 무슨 값이든 dp[i-1]이 음수이면, dp[i] = number[i]이다. 위 예시의 dp[3]에서 확인할 수 있다.

 

그리고 함수의 정의에 의해, dp 값들 중 최대 값이 답이 된다.

 

 

함수랑 점화식을 어떻게 잘 정의할 수 있을까?

경험의 영역인 것 같다. 나는 처음에 정말 모르겠어서 머리 깨져가면서 여러 문제 풀고, 이해하고, 다른 사람들 코드도 보니까 조금 익숙해졌다. dp는 몰아서 푸는 게 도움되는 것 같다.

 

 

코드

import kotlin.math.max

fun main() {
    val n = readLine()!!.toInt()
    val number = readLine()!!.trim().split(" ").map { it.toInt() }
    val dp = IntArray(n) { i -> number[i] }

    var answer = number[0]
    for (i in 1 until n) {
        if (dp[i - 1] < 0) dp[i] = number[i]
        else dp[i] = dp[i - 1] + number[i]
        // dp[i] = max(number[i], dp[i - 1] + number[i])와 같음
        
        answer = max(answer, dp[i])

        /* 틀렸던 코드
        if (0 <= number[i]){
            dp[i] = max(dp[i], dp[i-1] + number[i])
            answer = max(answer, dp[i])
        }
        */
    }

    println(answer)
}