Kotlin] 백준 14501번 문제풀이

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

14501번: 퇴사

 

 

(이 문제는 해당 블로거의 힘을 빌림.. dp 너무 못함 ^-ㅠ)

 

https://kdw999.tistory.com/210

[백준 / 14501 퇴사 / Java / DP]

 

 

배열에 이득을 저장한다

dp = Array<Int> { 0 }

 

n일 상담 끝났을 때의 날짜와 원래 저장되어있던 이득과 비교해서 최대 이득을 리턴한다.

예시와 함께 보자

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

 

퇴사는 n+1일에 하므로 퇴사 날보다 1이상 큰 배열을 만든다. 

 

1일차

1일차에 들어온 상담을 일단 받아보자. 상담이 끝나는 4일 차에 10의 이득을 얻는다. 원래 들어있던 이득인 0보다 10이 크므로 변경한다.

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

 

2일차

2일차에 들어온 상담을 일단 받아보자. 상담이 끝나는 2+5 =6일 차에 20의 이득을 얻는다. 원래 들어있던 이득인 0보다 20이 크므로 변경한다.

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

 

3일차

3일차에 들어온 상담을 일단 받아보자. 상담이 끝나는 3+1 =4일 차에 10의 이득을 얻는다. 원래 들어있던 이득인 10과 같으므로 변경하지 않는다.

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

 

4일차

4일차에 들어온 상담을 일단 받아보자. 상담이 끝나는 4+1 =5일 차에 20의 이득을 얻는다. 앞에 4일에 10의 이득이 있었으므로 얻을 수 있는 이득이 30이다. 원래 들어있던 이득인 0과 비교했을때 높으므로 변경한다

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

 

5일차

5일차에 들어온 상담을 일단 받아보자. 상담이 끝나는 5+2 =7일 차에 15의 이득을 얻는다. 앞에 6일에 30의 이득이 있었으므로 얻을 수 있는 이득이 45이다. 원래 들어있던 이득인 20과 비교했을때 높으므로 변경한다

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

 

6일차 , 7일차

는 퇴사날짜보다 길어 상담 할 수 없으므로 제외한다.

따라서, 최대 이득은 7일의 45가 된다.

 

이를 코드로 쓰면

import kotlin.math.max

fun main(args: Array<String>) {
    question14501()
}

fun question14501() {
    val day = readln().toInt()

    val list = mutableListOf<Consulting>()
    for (i in 1..day) {
        val require = readln().split(" ").map { it.toInt() }
        list.add(Consulting(require[0], require[1]))
    }

    val dp = Array(day + 1) { 0 }

// 날짜를 돌아본다.
    for (i in 0 ..< day) {
    // 현재 날짜 + 상담의 날짜가 퇴사날짜를 넘지 않도록 if문으로 판단
        if(i + list[i].day <= day) {
        // 현재 이득 + 상담이 끝났을 때의 이득의 합과 원래 이득을 비교하여 높은 것을 삽입한단.
            dp[i + list[i].day] = max(dp[i + list[i].day], dp[i] + list[i].price)
        }

		// 비교 계산을 할 수 있도록 다음 날과의 비교를 통해 최대 가격을 가져온다.
        dp[i+1] = max(dp[i+1], dp[i])
    }

    println(dp[day])


}

data class Consulting(
    val day: Int,
    val price: Int
)