백준 13398 연속합 2 Kotlin (dp)

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

13398번: 연속합 2

문제

n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다. 또, 수열에서 수를 하나 제거할 수 있다. (제거하지 않아도 된다)

예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 수를 제거하지 않았을 때의 정답은 12+21인 33이 정답이 된다.

만약, -35를 제거한다면, 수열은 10, -4, 3, 1, 5, 6, 12, 21, -1이 되고, 여기서 정답은 10-4+3+1+5+6+12+21인 54가 된다.

입력

첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

출력

첫째 줄에 답을 출력한다.

알고리즘 분류

• 다이나믹 프로그래밍

풀이

dp 문제이다.

2차원 dp, 1차원 dp 두 개의 풀이가 가능하다.

2차원 DP

dp[i][0] = 아무 숫자도 제거하지 않았을 때 i번까지의 최대 연속 합 

dp[i][1] = 어떤 숫자를 제거했을 때 i번까지의 최대 연속 합

 

우선 dp[i][0]을 구하는 점화식을 세워보자.

dp[i][0] = dp[i-1][0] + arr[i] vs arr[i]

dp[i-1][0] + arr[i] == i 이전까지의 연속 합의 최댓값에 i번 째 요소를 더한 값

arr[i] == i 번째 요소

아무것도 제거하지 않았을 때는 쉽게 점화식을 세울 수 있다.

 

dp[i][1]을 구하는 점화식을 세워보자.

dp[i][1] = dp[i-1][0] vs dp[i-1][1] + arr[i-1]

dp[i-1][0] == 이전까지 아무것도 제거하지 않았어서 i번 요소를 제거할 수 있는 경우

dp[i-1][1] + arr[i] == 이전에 무언가를 제거했어서 i번 요소를 제거하지 못하는 경우 i번 요소도 더해주어야 한다.

 

이렇게 두 가지 점화식을 이용해 2차원 dp를 채워주고 dp 안에서 가장 큰 값을 찾아주자.

주의할 점은 숫자가 음수로만 이루어진 경우도 있다는 점!

 

1차원 DP

이 풀이의 핵심은 다음과 같다.

i번째 요소를 삭제한다면 최댓값 = i번째 요소 이전까지의 최대 연속합 + i번 째 요소 이후까지의 최대 연속합

왼쪽부터의 최대 연속합 dp1, 오른쪽부터의 최대 연속합 dp2를 정의하고,

i번째 요소를 삭제한 경우 = dp1[i-1] + dp2[i+1]

그리고 요소를 삭제하지 않는 경우 중에서 최댓값 중에서 최댓값을 구해주면 된다.

 

 

코드1

val br = System.`in`.bufferedReader()
fun getIntList() = br.readLine().trim().split(' ').map { it.toInt() }
fun getInt() = br.readLine().trim().toInt()

fun main() = with(System.out.bufferedWriter()){
    //input
    val INF = 1_000_000_000
    val n = getInt()
    val arr = getIntList()
    val dp = Array(n+1){IntArray(2){-INF} }
    var answer = -INF
    for(i in 1 .. arr.size){
        dp[i][0] = (dp[i-1][0] + arr[i-1]).coerceAtLeast(arr[i-1])
        dp[i][1] = dp[i-1][0].coerceAtLeast(dp[i-1][1]+arr[i-1])
        answer = answer.coerceAtLeast(dp[i][0].coerceAtLeast(dp[i][1]))
    }
    write("$answer")

    close()
}

코드2

val br = System.`in`.bufferedReader()
fun getIntList() = br.readLine().trim().split(' ').map { it.toInt() }
fun getInt() = br.readLine().trim().toInt()

fun main() = with(System.out.bufferedWriter()){
    //input
    val INF = 1_000_000_000
    val n = getInt()
    val arr = getIntList()
    val dp1 = IntArray(n){-INF}
    val dp2 = IntArray(n){-INF}
    dp1[0] = arr[0]
    dp2[n-1] = arr[n-1]
    var answer = dp1[0]
    for(i in 1 until n){
        dp1[i] = arr[i].coerceAtLeast(dp1[i-1]+arr[i])
        dp2[n-i-1] = arr[n-i-1].coerceAtLeast(dp2[arr.size-i] + arr[arr.size-i-1])
        answer = answer.coerceAtLeast(dp1[i])
    }
    for(i in 1 until n-1){
        answer = answer.coerceAtLeast(dp1[i-1] + dp2[i+1])
    }
    
    write("$answer")

    close()
}