[백준/Swift] 14501번: 퇴사(DP)

 

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

14501번: 퇴사

 

N일동 안 최대한 많은 상담

상담에 걸리는 시간 Ti, 상담 시 금액 Pi

백준이가 얻을 수 있는 최대 수익은?

 

i일에 얻을 수 있는 최대 이익(dp[i]) 중 최대 이익 구하기

2중 for문

- i일에 상담해도 되는지 체크 (상담 기간 n일 넘으면 안 됨)

- i일에 상담한다고 했을 때, 얻는 금액

- 0~i-1일을 순회하면서

  - j일에 상담하면 i일에 상담할 수 있는지 체크

  - 상담할 수 있다면, 금액 합치기 -> 여기서 그동안 dp[i]에 저장된 금액과 비교해서 최대 금액으로 갱신

 

[DP]

import Foundation

//input
let n = Int(readLine()!)!
var arr = [(Int, Int)]() //기간, 이익
var dp = [Int](repeating: 0, count: 17)
for _ in 0..<n {
    let input = readLine()!.split(separator: " ").map { Int(String($0))! }
    arr.append((input[0], input[1]))
}
var answer = 0
for i in 0..<n {
    if arr[i].0 + i > n { continue } //이 날 상담해도 되는지 체크 (상담 기간이 n일 넘으면 안됨)
    dp[i] = arr[i].1 //이날 상담한다고 했을 때, 얻는 금액
    for j in 0..<i { //앞에서부터 확인하면서
        if arr[j].0 + j <= i { //그날 상담하면 i일에 상담할 수 있는지 체크
            dp[i] = max(dp[i], arr[i].1 + dp[j]) //그날의최대 이익에 더하기
        }
    }
    answer = max(answer, dp[i]) //최댓값
}
print(answer)
//print(dp.max()!) <- 이렇게 해도 24ms

 

전에 백트래킹으로도 풀었던 문제인데 이 문제는 백트래킹(12ms)이 더 빠르네.. DP(24ms)

흠.. n이 작아서 그런가

 

https://nyeoungkm.tistory.com/entry/백준Swift-퇴사

[백준/Swift] 14501번 퇴사