[백준] 15486 퇴사 2

문제

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

 

입력

n: Int = 남은 근무 일 
t: [Int] = 근무 시간
p: [Int] = 일급

1 <= n < 1,500,000

결과

ans: Int = 퇴사할 때 최대 수익

해석

점화식은 문제에서 금방 구할 수 있다.

dp[i] = i 날까지 왔을 때 최대 수익

 

j = i + t[i] = 다시 일을 할 수 있는 날 , i = 1이고, t[i] = 1이면 , 다음일은 2일부터 바로 시작할 수 있다.

 

하지만 여기서 중요한 점은 일을 많이한다고 수익이 최대가 아니다. 

 

그러므로 현재 i날을 기준으로 전날 까지의 최댓값을 계속 가져가야한다.

 

코드

import Foundation

var t: [Int] = [0]
var p: [Int] = [0]

let n = Int(readLine()!)!

for _ in 0..<n {
    let input = readLine()!.split{$0 == " "}.map{Int($0)!}
    t.append(input[0])
    p.append(input[1])
}

var dp: [Int] = [Int](repeating: 0, count: n+1)


for i in 1...n {
    dp[i] = max(dp[i-1], dp[i])// 전날 까지의 최댓값

    let time = t[i]
    let pay = p[i]
    
    let j = i + time-1 // 시작일도 포함이므로 -1
    
    if  j > n  { continue }
    
    dp[j] = max(dp[j], dp[i-1] + pay) // 전날 최대값 + 오늘 일
}


print(dp[n])