[백준/BOJ] 14501번: 퇴사

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

14501번: 퇴사

문제

상담원으로 일하고 있는 백준이는 퇴사를 하려고 한다.

오늘부터 N+1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다.

백준이는 비서에게 최대한 많은 상담을 잡으라고 부탁을 했고, 비서는 하루에 하나씩 서로 다른 사람의 상담을 잡아놓았다.

각각의 상담은 상담을 완료하는데 걸리는 기간 Ti와 상담을 했을 때 받을 수 있는 금액 Pi로 이루어져 있다.

N = 7인 경우에 다음과 같은 상담 일정표를 보자.

 1일2일3일4일5일6일7일TiPi

3	5	1	1	2	4	2
10	20	10	20	15	40	200

1일에 잡혀있는 상담은 총 3일이 걸리며, 상담했을 때 받을 수 있는 금액은 10이다. 5일에 잡혀있는 상담은 총 2일이 걸리며, 받을 수 있는 금액은 15이다.

상담을 하는데 필요한 기간은 1일보다 클 수 있기 때문에, 모든 상담을 할 수는 없다. 예를 들어서 1일에 상담을 하게 되면, 2일, 3일에 있는 상담은 할 수 없게 된다. 2일에 있는 상담을 하게 되면, 3, 4, 5, 6일에 잡혀있는 상담은 할 수 없다.

또한, N+1일째에는 회사에 없기 때문에, 6, 7일에 있는 상담을 할 수 없다.

퇴사 전에 할 수 있는 상담의 최대 이익은 1일, 4일, 5일에 있는 상담을 하는 것이며, 이때의 이익은 10+20+15=45이다.

상담을 적절히 했을 때, 백준이가 얻을 수 있는 최대 수익을 구하는 프로그램을 작성하시오.

해설

DP를 이용하여 문제를 해결하였다.

이중반복문을 만들어 처음에는 기준 일을 정하고 그 안에 기준 일까지의 최대 금액을 구할 수 있게 반복문을 만들었다.

for(i in 1 until day) {
    for(j in 0 until i) {
           if(i - j >= time[j]) dp[i] = max(cost[i] + dp[j], dp[i])
    }
}

위와 같이 기준일에서 현재일을 뺐을 때(i-j) time[j]보다 크다면 j에서의 일을 하고 i에서의 일을 할 수 있다는 것이다.

따라서 j까지의 최대 수익과 i의 수익을 더한 값과 i의 값만을 비교했을 때 더 큰 값을 dp에 저장해준다.

이 과정이 끝났다면 dp배열을 돌아보면서 i + time[i]를 한 값이 총 일 수를 넘어서지 않는지 확인해본다.

for(i in 0 until day) {
    if(i + time[i] <= day) {
        if(max < dp[i]) max = dp[i]
    }
}

만약 넘어가게 된다면 퇴사일을 넘어서서까지 일을 해야하기 때문이다.

소스 코드

import java.util.*
import kotlin.math.max

fun main() {
    val day = readLine()!!.toInt()
    val time = Array(day) { 0 }
    val cost = Array(day) { 0 }
    val dp = Array(day) { 0 }
    for(i in 0 until day) {
        val st = StringTokenizer(readLine())
        time[i] = st.nextToken().toInt()
        cost[i] = st.nextToken().toInt()
        dp[i] = cost[i]
    }
    for(i in 1 until day) {
        for(j in 0 until i) {
            if(i - j >= time[j]) dp[i] = max(cost[i] + dp[j], dp[i])
        }
    }
    var max = 0
    for(i in 0 until day) {
        if(i + time[i] <= day) {
            if(max < dp[i]) max = dp[i]
        }
    }
    println(max)
}