# 15486 퇴사 2

# 문제

---

 

# 코드

---

import kotlin.math.max

fun main() = with(System.`in`.bufferedReader()) {
    val n = readLine().toInt()
    val dp = IntArray(n + 1)
    repeat(n) { i ->
        val (t, p) = readLine().split(' ').map { it.toInt() }
        if (i + t <= n) dp[i + t] = max(dp[i] + p, dp[i + t])
        dp[i + 1] = max(dp[i], dp[i + 1])
    }
    println(dp[n])
}

 

 

# 풀이

---

 

처음에 작성한 코드는 아래 코드였다.

import kotlin.math.max

fun main() = with(System.`in`.bufferedReader()) {
    val n = readLine().toInt()
    val counsel = Array(n + 1) { mutableListOf<Pair<Int, Int>>() }
    val dp = IntArray(n + 1)
    repeat(n) { i ->
        val (t, p) = readLine().split(' ').map { it.toInt() }
        if (i + t <= n) counsel[i + t].add(i to p)
    }
    for (i in 1..n) {
        dp[i] = dp[i - 1]
        for (j in counsel[i].indices) {
            dp[i] = max(dp[i], dp[counsel[i][j].first] + counsel[i][j].second)
        }
    }
    println(dp[n])
}

 

어떤 방식으로 구현한 것이냐면

1. (시작날짜, 비용 p)쌍을 상담을 끝낼 수 있는 날짜에 추가한다.
   • 이렇게 하면 모든 입력에 대해 상담이 가능한 것들만 추려서 리스트에 저장이 된다.
2. 최대 값 구하기
   • 해당 날짜까지 끝낼 수 있는 상담이 있는 경우(리스트가 비어있지 않은 경우)
     • 해당 날짜까지의 최대값을 구함
   • 해당 날짜까지 끝낼 수 있는 상담이 없는 경우(리스트가 비어있는 경우)
     • 이전 날짜까지의 최대값이 해당 날짜의 최대값이 됨
3. N일까지 반복

이렇게 구현했을 때, 정답 처리가 됐지만, 굳이 pair를 안 써도 해결이 될 것 같았다.

 

그래서 dp만 사용해서 풀도록 코드를 수정했다.

repeat(n) { i ->
    val (t, p) = readLine().split(' ').map { it.toInt() }
    if (i + t <= n) dp[i + t] = max(dp[i] + p, dp[i + t])
    dp[i + 1] = max(dp[i], dp[i + 1])
}

이 부분의 코드를 살펴보자.

 

상담이 끝나는 날짜가 N일을 넘지 않도록 if문으로 처리해줬다.

 

dp[i+t] = max(dp[i] + p, dp[i+t])

이 부분을 예시를 들어보자.

1일째의 t = 3, p = 10 상담을 받는다고 했을 때, 상담은 3일째에 끝나기 때문에 dp[3] 부분에 저장된다.

1. 해당 상담을 받기 전 최대 값인 dp[0]에 해당 상담을 받은 후 비용인 10을 더한 값 dp[0]+10
2. 원래 dp[3] 부분의 값

이 두 가지를 비교해서 최대값을 저장해 두면 된다.

2번에 원래 dp[3] 부분과 비교하는 이유는, 3일째에 끝나는 상담이 여러 개일 수 있기 때문이다.

 

그리고 dp[i+1] = max(dp[i], dp[i+1]) 부분은

해당 날짜에 끝나는 상담이 없을 때 dp 값을 갱신해주기 위해서다.

이전 날짜의 최대 값이 현재 날짜의 최대 값이 되기 때문

 

전체 코드는 위의 코드 부분 참고