[백준 1912번] [Kotlin] 연속합

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

1912번: 연속합

 

난이도 : 실버 2
태그 : 다이나믹 프로그래밍

 

 

문제 접근

 

이 문제는 처음 값부터 특정 값까지 가장 큰 부분을 찾는 문제가 아니라,

값이 최대가 되는 특정 구간을 찾는 문제입니다.

10 -4 3 1 5 6 -35 12 21 -1

예제에서는 12~21 부분이 되겠네요.

 

1 ~ 1 구간 : 10

1 ~ 2 구간 : 6

1 ~ 3 구간 : 9

1 ~ 4 구간 : 10

1 ~ 5 구간 : 15

1 ~ 6 구간 : 21

1 ~ 7 구간 : -14

여기서 8번째 값에 도달할 때,

1 ~ 8 구간인 2보다 그냥 8번째 값인 12가 더 큽니다.

즉, 1 ~ 8 구간합은 그냥 다 버리면 되고, 8번째 값 부터 새로 시작하면 됩니다.

정리하자면, 이전 구간합 + (현재 값) 보다 현재 값이 더 크다면, 이전 구간합을 다 버립니다.

 

 

소스코드

import java.util.*
import kotlin.math.max

fun main() = with(System.`in`.bufferedReader()) {
    val n = readLine().toInt()
    val st = StringTokenizer(readLine())
    val arr = Array(n) { st.nextToken().toInt() }
    val dp = Array(n) { 0 }

    dp[0] = arr[0]
    var max = arr[0]

    for (i in 1 until n) {
        dp[i] = max(dp[i - 1] + arr[i], arr[i])
        max = max(max, dp[i])
    }

    println(max)
}

 

 

후기

어떻게 풀어야 할 지 감은 잡히는데, 코드가 잡히질 않아 질문 게시판을 탐색한 끝에 푼 문제입니다.

체감상 다이나믹 프로그래밍 문제는 실버 2가 다른 문제 골드 3 정도 되는 것 같습니다...