[백준/Python] 14501번: 퇴사

문제

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

14501번: 퇴사

---

문제 요약

상담원으로 일하고 있는 백준은 퇴사를 하려고 한다.

 

오늘부터 N+1일째 되는 날, 퇴사를 하기 위해서 남은 N일 동안 상담을 통해 낼 수 있는 최대 수익을 출력한다.

 

각각의 상담은 상담을 완료하는데 걸리는 시간 Ti와 상담을 했을 때 받을 수 있는 금액 Pi로 이루어져 있다.

 

+ 상담을 하는 기간동안은 다른 상담을 할 수 없다.

---

코드

N = int(input())

schedule = [list(map(int, input().split())) for _ in range(N)]
# 0일 ~ N - 1일
# schedule[i]는 i일에 상담 일정, [Ti, Pi]
# Ti는 상담을 완료하는데 걸리는 기간
# Pi는 상담을 했을 때 받을 수 있는 금액

res = 0

dp = [0] * (N + 1)
# dp[i]는 i - 1일까지의 상담으로 받을 수 있는 최대 금액 (일을 마친 다음 날 돈을 받을 수 있다.)
# dp[0]은 사용 x

for i in range(N):
    # i일까지 일한 돈을 받고, i일에 상담해서 받을 돈을 갱신 (i일 이후 모든 날짜에 갱신)
    for j in range(i + schedule[i][0], N + 1):
    # j는 i번째 날에 상담을 했을 때, 상담이 가능한 모든 날짜 (상담을 쉴 경우)
        dp[j] = max(dp[j], dp[i] + schedule[i][1])
        #print(dp)
print(dp[N])

---

코드 설명

편의상 0일 ~ N-1일까지 상담할 수 있다고 가정한다.

 

1. N - 1일까지의 상담 정보를 2차원 배열 schedule에 저장한다.

 

2. dp[i]가 i - 1일까지의 상담으로 받을 수 있는 최대 금액을 저장하는 메모이제이션 테이블 dp를 생성한다.

+ i - 1일까지 상담을 마쳐야 i일에 돈을 받을 수 있다.

 

3. i일의 상담을 마치고 다른 상담이 가능한 모든 날짜(i일 이후 모든 날짜) j의 dp값을 갱신한다.

+ i - 1일까지 상담으로 번 금액 + i일의 상담으로 번 금액 vs 기존 j일까지 상담으로 번 금액

 

4. N - 1일까지의 상담으로 벌 수 있는 최대 금액 dp[N]을 출력한다.