[백준] 안녕 (1535)(kotlin)

문제 설명

백준 1535번 문제 링크

입력 및 출력

» 입력

첫째 줄에 사람의 수 N(<=20)이 들어온다. 둘째 줄에는 각각의 사람에게 인사를 할 때, 잃는 체력이 1번 사람부터 순서대로 들어오고, 셋째 줄에는 각각의 사람에게 인사를 할 때, 얻는 기쁨이 1번 사람부터 순서대로 들어온다. 체력과 기쁨은 100보다 작거나 같은 자연수 또는 0이다.

» 출력

첫째 줄에 세준이가 얻을 수 있는 최대 기쁨을 출력한다.

예제 입출력(테스트케이스)

입력	출력
3 1 21 79 20 30 25	50

문제 풀이1

풀이 참고

import java.util.Scanner

fun main(args: Array<String>) = with(Scanner(System.`in`)) {
    val N = nextInt()
    val loses = IntArray(N + 1)
    val gains = IntArray(N + 1)
    val dp = Array(N + 1) { IntArray(100) }

    for (i in 1 until N + 1) {
        loses[i] = nextInt()
    }

    for (i in 1 until N + 1) {
        gains[i] = nextInt()
    }

    for (i in 1..N) {
        for (hp in 99 downTo 1) {
            dp[i][hp] = if (loses[i] <= hp && dp[i - 1][hp - loses[i]] + gains[i] > dp[i - 1][hp]) {
                dp[i - 1][hp - loses[i]] + gains[i]
            } else {
                dp[i - 1][hp]
            }
        }
    }

    println(dp[N][99])
}

문제 풀이1(해설)