[백준 15486] - 퇴사2(Kotlin)[골드5]

문제

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

15486번: 퇴사 2

 

문제 풀이

DP의 대표적인 유형이다.

DP는 항상 DP 배열이 무엇을 의미하는지 정하는 것이 가장 중요하다.

내가 정한 DP 배열은 다음과 같다.

DP[i]는 i일에 벌 수 있는 최대 금액

 

1일	2일	3일	4일	5일	6일	7일
3	5	1	1	2	4	2
10	20	10	20	15	40	200

문제에서 주어진 예시는 다음과 같다.

우리는 N일까지의 상담을 바탕으로 금액을 계산하면 된다.

 

DP [상담을 시작하는 일 + 상담하는 데 걸리는 기간] = 상담하는데 버는 비용 

예를 들어서 첫날에 상담을 하면 DP[1+3] = 10이 될 것이다.

두 번째 상담을 하면 DP [2+5] = 20이 될 것이다.

다음 3일 차가 특별한 경우이다. 

1일 차에서 상담을 할 경우 4일 차에 끝나고, 3일차에 상담을 시작하면 4일차에 끝난다. 이 두 경우의 수 중 최대의 이익을 벌 수 있는 경우를 택해야 한다.

따라서 점화식은 다음과 같다.

DP [now+day ] =max(DP [now+day], DP [now]+cost)

 

코드

package Baekjoon.DP.`15486`

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

class `15486` {
    val br =BufferedReader(InputStreamReader(System.`in`))
    var N = 0
    var schedule : ArrayList<Pair<Int,Int>> = ArrayList()
    lateinit var dp : Array<Int>
    init{
        input()
        print(solution())
    }
    fun input(){
        N = br.readLine().toInt()
        dp = Array(N+2,{ 0 }) //N+50이 최대일거같음.
        for(i in 0 until N){
            val line = br.readLine().split(" ")
            schedule.add(Pair(line[0].toInt(),line[1].toInt()))
        }
        schedule.add(Pair(0,0))
    }
    fun solution() : Int{
        for (j in 1 .. N) { //1일부터 N일까지
            dp[j] = max(dp[j-1],dp[j])
            if(j+schedule[j-1].first > N+1) //넘는다면
                continue
            dp[j+schedule[j-1].first] = max(dp[j]+ schedule[j-1].second, dp[j+schedule[j-1].first])
        }
        return dp.maxOrNull()!!
    }
}
fun main(){
    val solution = `15486`()
}