(Kotlin) 백준 14501 - 퇴사

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

14501번: 퇴사

 

문제유형: DP

접근 방법

DP 문제라는 걸 알고 접근했는데 처음에 해결법이 떠오르지 않았다. 여러 블로그를 참고해서 이해했는데, 그것을 토대로 생각해낸 접근법은 다음과 같다.

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

 

위의 문제 지문에서 힌트를 얻을 수 있는데, 특정 날짜에 상담을 하느냐 안하느냐에 따라 결과가 달라진다.

a[i]의 의미를 i일부터 n일까지 얻을 수 있는 이익이라고 정의한다면, 경우의 수를 2가지로 나눌 수 있다.

 

1. i일에 일을 안하는 경우
2. i일에 반드시 일을 반드시 하는 경우.

점화식 :  price[i] = max( price[i+1], price[i] + price[ i + time[i] ] )

• if ( n+1 < i + time[i] ) -> price[i] = price[i+1]: 해당 날짜에 상담했을 때 제때 퇴사할 수 없다면, 그 날짜엔 일을 하지 않는다.  

n = 7이고 T[7] = 1일 때 (i + time[i]) = 8 > 7이지만, 7일에도 상담이 가능하다.

따라서, 배열 크기를 n+2, 초기값 price[n+1] = 0으로 초기화 해주면 i = n부터 반복문을 시작할 수 있다.

코드

fun main(){
    val n = readLine()!!.toInt()
    val time = IntArray(n+2)
    val price = IntArray(n+2)

    for (i in 1..n){
        val numbers = readLine()!!.split(" ").map{ it.toInt() }
        time[i] = numbers[0]
        price[i] = numbers[1]
    }
    price[n+1] = 0	// 초기값

    for (i in n downTo 1){
        if ( n+1 < i + time[i] ){	// 예외처리
            price[i] = price[i+1]
            continue
        }

        price[i] = max(price[i+1], price[i] + price[ i + time[i] ])	// 점화식
    }

    println(price[1])
}

리뷰

• dp 기분 문제였지만 해결법을 떠올리고, 풀이를 이해하는 게 쉽지 않았다.
• 바텀업 방식을 하향식으로 생각해볼 수도 있구나.
• 꾸준히 풀어서 익숙해져야지.