[다이나믹 프로그래밍 + 구현] 백준 실버3 14501번: 퇴사(Swift)

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

14501번: 퇴사

풀이과정

이번 문제는 주어진 백준이 주어진 N + 1일 동안 업무를 했을 때 벌 수 있는 최대 누적 금액을 구하는 문제이다.

최대 누적 금액을 구하는 문제이기 때문에 DP를 활용하면 쉽게 접근할 수 있겠다는 생각이 들었다.

처음엔, DP 배열에 일차 별로 벌 수 있는 최대 누적 금액을 담으려 했지만, 그러면 일을 시작하고 끝나는 날을 카운팅 하기 쉽지 않았다.

때문에 끝나는 날을 기준으로 DP에 누적 금액을 담았다.

예를 들어, 1일차 상담을 시작하면 상담이 끝나는 날은 4일이다.

때문에 DP[4]에 해당 금액을 담는다.

이런 식으로 DP에 최대 누적금액을 저장하여 문제를 해결하였다.

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

for i in 1...N {
  let TP = readLine()!.split(separator: " ").map { Int($0)! }
  
  if i+TP[0] > N + 1 { continue }
  
  dp[i + TP[0]] = max(TP[1] + dp[1...i].max()!, dp[i + TP[0]])
}

print(dp.max()!)

i는 일차에 해당하는 값이고,

TP[0] = 상담에 걸리는 시간

TP[1] = 금액

먼저, 반복문을 통해 상담에 걸리는 시간과 금액을 입력받는다.

다음, DP에 일차와 상담에 걸리는 시간을 더해서 상담을 시작해서 끝나는 날 기준으로 DP에 누적 최대 금액을 담는다.

최대 누적 금액은 기존에 DP에 담겨있던 값과 해당 일차의 금액과 DP 배열 [1... i] 범위에 가장 큰 값을 더해준 값을 비교한다.

DP 배열은 해당 일차 기준으로 상담을 완료했을 때의 값이기 때문에 범위를 정해 그 범위 중에서 가장 큰 값과 해당 일차의 금액을 더한 값이 최댓값이 된다.

여기서, 일차 + 상담에 걸리는 시간 값이 N + 1보다 크면 업무를 볼 수 없기 때문에 계산에서 제외한다.

반복문이 종료되면, DP에서 최댓값을 뽑아내면 문제를 해결할 수 있다.