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

출처: unsplash.com

 

연속합(1912번)

Silver 2

#다이나믹 프로그래밍

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

 

문제 내용

 

 

문제 접근

정수들이 주어지면, 연속된 정수의 합 중의 최댓값을 찾아서 출력한다.

시간제한이 1초이고, 정수는 10만 개까지 들어오기 때문에 다이나믹 프로그래밍이 강제된다.

이 문제를 다이나믹 프로그래밍으로 풀기 위해서는 어떻게 해야 할까?

 

입력 예제 1을 예로 들어 보겠다.

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

정수를 하나씩 보면서 최댓값을 찾아보자.

 

첫 번째 수는 10이기 때문에 연속된 수의 합은 10이다.

두 번째 수는 -4이다. 연속된 수의 합은 6이다. 6과 -4중에 6이 더 크다.

세 번째 수는 3이다. 연속된 수의 합은 9이다. 9와 3중에 9가 더 크다.

네 번째 수는 1이다. 연속된 수의 합은 10이다. 10과 1중에 10이 더 크다.

다섯 번째 수는 5이다. 연속된 수의 합은 15다. 15과 5중에 15가 더 크다.

여섯 번째 수는 6이다. 연속된 수의 합은 21이다. 21과 6중에 21이 더 크다.

일곱 번째 수는 -35다. 연속된 수의 합은 -14이다. -14와 -35중에 -14가 더 크다.

여덟 번째 수는 12이다. 연속된 수의 합은 -2이다. -2와 12중 12가 더 크다. 연속된 수의 합을 12로 변경한다.

아홉 번째 수는 21이다. 연속된 수의 합은 33이다. 33과 21중 33이 더 크다.

열 번째 수는 -1이다. 연속된 수의 합은 32이다. 32와 -1중 32가 더 크다.

 

총 10번의 탐색 결과에서 정답이 있다. 정답은 33이다.

위와 같은 방식으로 답을 구하면 최댓값이 포함되어 있는 리스트를 얻을 수 있다.

그 리스트에서 최댓값을 구해주면 된다.

 

점화식은 다음과 같이 구성한다.

max(res[i - 1] + numbers[i], numbers[i])

res가 현재까지의 최댓값이고, numbers가 입력받은 정수들일 때, 두 수의 합이 연속된 수의 합이다.

연속된 수의 합과 입력 정수 중 더 큰 값을 찾는다.

 

 

문제 해결 코드

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

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val numberCnt = readLine().toInt()
    val numbers = readLine().split(" ").map { it.toInt() }
    val res = Array(numberCnt) { 0 }
    res[0] = numbers[0]

    for (i in 1 until numbers.size) {
        res[i] = max(res[i - 1] + numbers[i], numbers[i])
    }

    println(res.max())
}

 

문제 풀이

입력받은 정수들의 최댓값을 res에 저장할 것이다. res의 초기 값인 0번째 값은 입력받은 정수들의 첫 번째 정수로 지정한다.

그리고 반복하면서 최댓값을 구해 준다.

 

 

문제 해결 과정

평범한 다이나믹 프로그래밍 문제.

일단 나는 처음에 점화식이 생각이 안 나서 문제 게시판을 참고했다.

언제쯤 다이나믹 프로그래밍을 마스터할 수 있을까?