[2023-04-20] 1912 연속합 (Kotlin)

 

문제 링크: https://www.acmicpc.net/problem/1912

1912번: 연속합

 

 

첫 번째 시도입니다.

 

 

package nineteenthDay
import java.io.*
fun main(){
    val br = BufferedReader(InputStreamReader(System.`in`))
    val n = br.readLine().toInt()
    val list = br.readLine().split(' ').map{it.toInt()}
    val arr = Array(n){0}
    var sum = 0
    // 누적 합을 arr 배열에 저장
    for (index in list.indices){
        sum += list[index]
        arr[index] = sum
    }
    // 이중 반복문을 통해 최대값을 조사
    var max = 0
    for (index in arr.indices){
        for (index1 in index until arr.size){
            if (index != 0){
                val value = arr[index1] - arr[index-1]
                if (max < value)
                    max = value
            }
            else{
                val value = arr[index1]
                if (max < value)
                    max = value
            }
        }
    }
    println(max)
}// 10 6 9 10 15 21 -14 -2 19 18

 

당연하게도 시간 초과가 떴습니다.

 

DP 유형을 스스로 풀어보고자 시간을 많이 썻지만,

 

결국 다른 분의 풀이를 참고하게 되었습니다.

 

 

// 누적합을 계속 진행하다가
// 누적합이 원래의 요소보다 작을 경우 초기화
// ex) 10 -4 3 1 5 6 -35 12 21 -1
//  0번 째 누적합 = 10
//  1번 째 누적합 = 6
//  2번 째 누적합 9
// ...
//  8번 째 누적합 -2
//  이 때 누적합이 원래 요소인 12보다 작으므로
//  12 부터 다시 누적합 구하기

fun main(){
    val br = BufferedReader(InputStreamReader(System.`in`))
    val n = br.readLine().toInt()
    val list = br.readLine().split(' ').map{it.toInt()}
    val arr = Array(n){0}
    val dp = Array(n){0}
    var sum = 0
    dp[0] = list[0]
    var max = list[0]
    for (index in 1 until n){
        dp[index] = Math.max(dp[index - 1] + list[index], list[index])
        max = Math.max(max, dp[index])
    }
    println(max)
}

 

 

동적 계획법이 모든 유형 중에서 가장 어려운 것 같아요.