백준 14501- 퇴사(kotlin)

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

14501번: 퇴사

문제 접근

• 주어진 날짜안에 상담을 진행하여 얻을 수 있는 최대 수익을 구하는 문제이다.
• 전체 날짜를 1일찍 상담을 할지말고 선택하는 dp문제인것 같다.
• 각 날짜에 상담을 진행할지말지를 선택할 수 있고 전체 날짜를 n이라 했을 때 시간 복잡도는 O(2^n)(1<=n<=15)이다.

재귀함수를 통해 모든 경우의 수를 탐색하였다.

 

정답 코드

import java.util.Scanner

var T = IntArray(0)
var P = IntArray(0)
var n = 0
var max = 0
fun main(args: Array<String>): Unit = with(Scanner(System.`in`)) {
    n = nextInt()
    T = IntArray(n + 1)
    P = IntArray(n + 1)

    for (i in 1..n) {
        T[i] = nextInt()
        P[i] = nextInt()
    }
    consulting(1, 0)
    print(max)
}

fun consulting(day: Int, sum: Int) {


    if (day == n + 1) {
        if (max < sum) max = sum
        return
    }
    if (day > n + 1) return



    consulting(day + T[day], sum + P[day])
    consulting(day + 1, sum)

}