[BOJ] 백준 15486 퇴사 2 풀이 (swift)

퇴사 2

풀이 (DP)

dp배열을 N+1 칸 만큼의 배열로 초기화를 합니다. 아래와 같이 예제 입력이 들어왔을 때
7
3 10
5 20
1 10
1 20
2 15
4 40
2 200

날짜 1 (now = 0):
상담 일수 T = 3, 이익 P = 10 1일차 상담을 하면 3일 후인 4일차에 이익을 얻게 됨.
dp[4] = max(dp[4], dp[1] + 10) -> dp[4] = 10
그리고 현재까지 이익은 유지해야 하므로 dp[1] = max(dp[1], dp[0]) -> dp[1] = 0
dp 상태: [0, 0, 0, 0, 10, 0, 0, 0]

날짜 2 (now = 1):
상담 일수 T = 5, 이익 P = 20 2일차 상담을 하면 7일 후에 이익을 얻게 됨.
dp[7] = max(dp[7], dp[2] + 20) -> dp[7] = 20
현재까지 이익 유지: dp[2] = max(dp[2], dp[1]) -> dp[2] = 0
dp 상태: [0, 0, 0, 0, 10, 0, 0, 20]

날짜 3 (now = 2):
상담 일수 T = 1, 이익 P = 10 3일차 상담을 하면 4일 후에 이익을 얻게 됨.
dp[4] = max(dp[4], dp[3] + 10) -> dp[4] = max(10, 0 + 10) -> dp[4] = 10 (변화 없음)
현재까지 이익 유지: dp[3] = max(dp[3], dp[2]) -> dp[3] = 0
dp 상태: [0, 0, 0, 0, 10, 0, 0, 20]

날짜 4 (now = 3):
상담 일수 T = 1, 이익 P = 20 4일차 상담을 하면 5일 후에 이익을 얻게 됨.
dp[5] = max(dp[5], dp[4] + 20) -> dp[5] = max(0, 10 + 20) -> dp[5] = 30
현재까지 이익 유지: dp[4] = max(dp[4], dp[3]) -> dp[4] = 10
dp 상태: [0, 0, 0, 0, 10, 30, 0, 20]

날짜 5 (now = 4):
상담 일수 T = 2, 이익 P = 15 5일차 상담을 하면 7일 후에 이익을 얻게 됨.
dp[7] = max(dp[7], dp[5] + 15) -> dp[7] = max(20, 30 + 15) -> dp[7] = 45
현재까지 이익 유지: dp[5] = max(dp[5], dp[4]) -> dp[5] = 30
dp 상태: [0, 0, 0, 0, 10, 30, 0, 45]

날짜 6 (now = 5):
상담 일수 T = 4, 이익 P = 40
6일차 상담은 10일차에 완료되므로 퇴사 후가 되어 상담을 할 수 없음.
현재까지 이익 유지: dp[6] = max(dp[6], dp[5]) -> dp[6] = 30
dp 상태: [0, 0, 0, 0, 10, 30, 30, 45]
날짜 7 (now = 6):

상담 일수 T = 2, 이익 P = 200
7일차 상담도 퇴사일 이후에 완료되므로 상담을 할 수 없음.
현재까지 이익 유지: dp[7] = max(dp[7], dp[6]) -> dp[7] = 45
dp 상태: [0, 0, 0, 0, 10, 30, 30, 45]

퇴사일을 넘기지 않는 선에서 최대의 이익을 얻는 방법으로 퇴사일까지 얻을 수 있는 최대 이익은 45

import Foundation

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

for now in 0..<N {
    let input = readLine()!.split(separator: " ").map { Int($0)! }
    let T = input[0]
    let P = input[1]
    
    dp[now + 1] = max(dp[now + 1], dp[now])		// 현재까지 얻은 최대 이익을 그 다음 날로 넘겨줌 (현재까지 계산한 최대 이익 유지)
    
    if now + T < N + 1 {        // 현재 상담을 진행할 수 있을 때만 (상담을 끝내는 날짜가 퇴사 날짜를 넘지 않을 경우)
        dp[now + T] = max(dp[now + T], dp[now] + P)
        print(dp[now + T])
    }
}
print(dp[N])

읽어주셔서 감사합니다! 오타 및 잘못된 내용은 언제든 댓글 달아주시면 최대한 빠르게 수정하겠습니다!