[백준 14501번] [Kotlin] 퇴사

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

14501번: 퇴사

 

난이도 : 실버 3
태그 : 다이나믹 프로그래밍, 브루트포스 알고리즘

 

 

설명

다이나믹 프로그래밍 (DP, Dynamic Programming)을 연습하기 좋은 문제인 것 같습니다.

동적계획법 혹은 다이나믹 프로그래밍은 메모리에 값을 저장해놨다가, 다음 연산에서 이전에 계산했던 값을 이용해

효율적으로 계산하는 프로그래밍 패러다임으로써,

 

메모리에 값을 저장해놓고 동일한 반복계산을 줄인다는 메모이제이션(Memoization)에 기반을 두고 있습니다.

 

 

 

 

백준의 예제를 가져왔습니다.

1일째에는 3일의 시간이 걸리므로, 4일에 10의 비용을 얻을 수 있습니다.

 

 

즉, 1일차 상담을 진행했을 때, 각 날짜별 최대 비용은 다음과 같습니다.

1일)

1	2	3	4	5	6	7
0	0	0	10	10	10	10

 

 

2일차 상담을 수락해봅시다. 2일차 상담은 5일이 걸리며, 7일에 20의 비용을 얻을 수 있습니다.

2일)

1	2	3	4	5	6	7
0	0	0	10	10	10	20

2일차의 현재 금액(0)과, 2일차 상담을 수락했을 때(20)을 더하면 7일차에 20을 얻을 수 있습니다.

 

3일)

1	2	3	4	5	6	7
0	0	0	10	10	10	20

3일차의 상담을 수락하면, 4일차에 10의 비용을 얻게 됩니다.

이미 4일차에 얻을 수 있는 금액은 10이므로, 업데이트 하지 않아도 됩니다.

 

4일)

1	2	3	4	5	6	7
0	0	0	10	30	30	30

4일차의 상담을 수락하면 5일차에 20의 비용을 얻습니다.

즉, 5일차의 비용은 기존의 값(10)과,

4일차에 기존에 있던 비용 (10) + 새로 얻게 될 비용(20) = 30중 더 큰 값으로 업데이트 하면 됩니다.

 

5일)

1	2	3	4	5	6	7
0	0	0	10	30	30	45

5일차 상담을 수락하면 2일 뒤 7일에 15를 얻게 됩니다.

기존에 7일에 얻을 수 있는 비용은 30이였습니다.

하지만, 5일차에서 기존에 있던 비용 30에 2일 뒤 얻게 될 비용 15를 더한 45가 더 크므로 업데이트를 해줍니다.

 

6, 7일차는 일을 수행하면 퇴사일을 넘기므로 확인하지 않습니다.

위 과정을 수행하면, 최종적으로 받을 수 있는 가장 큰 금액은 45가 됩니다.

 

 

 

소스코드

fun main() = with(System.`in`.bufferedReader()) {
    val n = readLine().toInt()

    // 1일에 잡힌 상담 -> arr[0]일, arr[1]원
    val arr = Array(n) { readLine().split(" ").map { it.toInt() } }
    val dp = Array(n + 1) { 0 }

    for (i in 0 until n) {
        if (i + arr[i][0] <= n) {
            if (i > 0) dp[i] = maxOf(dp[i], dp[i - 1])
            dp[i + arr[i][0]] = maxOf(dp[i + arr[i][0]], dp[i] + arr[i][1])
        }
    }

    println(dp.maxOrNull()!!)
}

 

 

 

후기

다이나믹 프로그래밍은 사실 그닥 다이나믹(동적)과는 큰 관련이 없습니다.

그냥 투자를 받기 좋을 것 같아서 붙인 이름이라 하네요.