[백준][KOTLIN][14501] 퇴사

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

14501번: 퇴사

문제 풀이

1. 문제에서 주어지는  N 이 15까지 주어져 있다.

2. 2^15 을 다 탐색해도 1억이 넘지 않아 시간 초과가 발생하지 않으므로 DFS 를 통해서 완전 탐색한다.

3. 탐색 시 2가지 경우에 대해서 탐색 한다.

3-1. 면담을 시작할 경우 : DFS(Day + T[Day], Sum + P[Day])

3-2. 면담을 하지 않고 다음 날로 넘어간 경우 : DFS(Day + 1, Sum)

4. 3번의 과정을 모두 탐색하고 Day 가 N보다 크거나 같을 경우 면담을 완료하고 퇴사를 한 경우이므로 최대 값인 지를 결과에 저장한다.

이때 Day 가 N 보다 클 경우는 면담 소요 시간이 N 보다 큰 경우이므로 면담을 진행할 수 없으므로 최대값을 구하지 않는다.

코드

import java.io.*

var result14501 = Int.MIN_VALUE

fun main(args: Array<String>) {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val N = br.readLine().toInt()
    val T = IntArray(N) { 0 }
    val P = IntArray(N) { 0 }
    repeat(N) {
        val (t, p) = br.readLine().split(" ").map { it.toInt() }
        T[it] = t
        P[it] = p
    }

    dfs(N, T, P, 0, 0)
    println(result14501)
}

fun dfs(N: Int, T: IntArray, P: IntArray, start: Int, sum: Int) {
    if (start == N) {
        result14501 = Math.max(result14501, sum)
        return
    }

    if (start > N) {
        return
    }

    dfs(N, T, P, start + T[start], sum + P[start])
    dfs(N, T, P, start + 1, sum)
}