백준 4097 수익 Kotlin (dp)

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

4097번: 수익

문제

연종이는 창업했다. 오늘은 창업한지 N일이 되었고, 매일 매일 수익을 적어놓았다.

어느 날 연종이는 가장 많이 돈을 번 구간이 언제인지 궁금해졌다.

오늘이 창업한지 6일 되었고, 수익이 다음과 같다고 하자.

• 1일: -3
• 2일: 4
• 3일: 9
• 4일: -2
• 5일: -5
• 6일: 8

이때, 가장 많은 돈을 번 구간은 2~6까지이고 총 수입은 14이다.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 N이 주어져 있다. (1 ≤ N ≤ 250,000) 둘째 줄부터 N개의 줄에는 매일 매일의 수익 P가 주어진다. (-10,000 ≤ P ≤ 10,000) 수익은 첫 날부터 순서대로 주어진다. 입력의 마지막 줄에는 0이 주어진다.

출력

각 테스트 케이스에 대해서 가장 많은 수익을 올린 구간의 수익을 출력한다. 단, 구간이 비어있으면 안 된다.

알고리즘 분류

• 다이나믹 프로그래밍

풀이

간단한 dp 문제다.

dp[i] = i번째 날까지 최대 수익이라는 식을 세운다.

그러면 dp[i]에 들어갈 값은 (0 + i번째 날의 수익) vs (i-1번째 날의 최대 수익 + i번째 날의 수익) 중 큰 값을 저장하면 된다.

따라서 점화식은 dp[i] = max(input[i-1], dp[i-1] + input[i-1])이 되고,

dp[n]이 정답이라는 보장이 없기 때문에 answer라는 변수를 두어 중간에 dp[1~n]중에서 최댓값을 저장한다.

 

i번째 날의 수익이 input[i-1]인 이유는 input은 인덱스 0부터 시작, dp는 인덱스 1부터 시작하게 만들었기 때문이다.

dp[n]이 정답이라는 보장이 없는 이유는, 1, -2 ,-6 같은 입력이 들어온다면 위의 점화식으론 dp[n]에 1이란 정답이 들어가지 않기 때문이다. 

 

코드

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

fun main() = with(System.out.bufferedWriter()) {
    //input
    while(true){
        val n = getInt()
        if(n == 0) break
        val input = IntArray(n){ getInt()}
        val dp = IntArray(n+1)
        var answer = -10000
        for(i in 1 .. n){
            dp[i] = input[i-1].coerceAtLeast(dp[i-1] + input[i-1])
            answer = answer.coerceAtLeast(dp[i])
        }
       write("$answer\n")
    }
    close()
}