[Kotlin] 백준(BOJ) 1912 연속합

문제 전문은 아래 버튼을 눌러 확인하실  수 있습니다.

문제

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

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

 

입력

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

 

출력

첫째 줄에 답을 출력한다.

 

예제 입출력

 

문제 해설

해당 문제는 연속한 구간의 합이 최대일 때 그 합을 구하는 문제이다. 다음과 같이 해결할 수 있었다. 

리스트를 순회하며 일단 더하면서 누적 합의 후보를 검사한다. 

후보 유효성은 다음과 같이 구할 수 있다. 

현재 인덱스의 리스트 값을 더한 결과가 현재 인덱스의 리스트 값보다 작은가? 

만약 작다면, 이전 결과를 버리고, 현재 인덱스의 리스트값 부터 시작하는 것이 최적해다. 

예를 들면 $-1, 5, 1, 2$의 수열이 있다고 할 때, $-1$에서 $5$를 더하면 $4$ 즉 $5(현재\ 값)$보다 $4(누적\ 합 + 현재\ 값)$가 작음을 알 수 있다. 때문에 $-1$을 버린다. 

 

소스 코드

fun main() {
    val sequenceSize = readln().toInt()
    val sequence = readln().split(" ").map { it.toInt() }

    var current = sequence[0]
    var answer = sequence[0]

    for (i in 1 until sequenceSize) {
        current = maxOf(sequence[i], current + sequence[i])
        answer = maxOf(answer, current)
    }

    println(answer)
}

 

 

 

시간 복잡도

for문 내에서 max연산을 2회, 즉 상수 번 수행하므로 $O(N)$이라고 할 수 있겠다.