백준 - 퇴사 (14501)

let N = Int(readLine()!)!
var data = [[0, 0]]
var dp = Array(repeating: 0, count: N + 2)

for _ in 0..<N {
    let input = readLine()!.split(separator: " ").map { Int(String($0))! }
    data.append(input)
}

for i in (1...N).reversed() {
    let t = data[i][0]
    let p = data[i][1]
    if i + t - 1 > N {
        dp[i] = dp[i + 1]
    } else {
        dp[i] = max(dp[i + 1], p + dp[i + t])
    }
}

print(dp[1])

그림을 그려보면 이해가 쉽다.

N일차부터 거꾸로 내려가면서 보면 현재 날짜부터 N일까지의 최대 이익은 max(현재 날짜에서 받을 수 있는 금액 + 현재 날짜에서 상담 기간이 지난 후부터 N일까지에서 최대로 받을 수 있는 금액, 현재 날짜 당므 날에서 받을 수 있는 최대 금액) 이 된다.

인덱스 범위가 초과되지 않도록 dp 배열의 크기를 N+2 로 설정한 다음 상담 기간이 퇴사일을 넘어가면 다음 날 최대 금액을 저장하고, 그렇지 않다면 위에서 말한 대로 점화식을 사용해서 최대 금액을 구해준다.