BOJ - 퇴사 14501번 (python)

❓ 문제 - 백준 퇴사 14501번 - python 풀이법

출처 

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

14501번: 퇴사

 

 

 

📝 문제해결법

1. 이 문제는 DP(동적계획법)으로 풀었다.

• 뒤에서 부터 탑다운 방식으로 상담 비용의 최대 이윤을 구한다.
• 만약 i일에 상담할 때 퇴사 날짜를 넘으면 해당 날짜에 상담을 시작할 수 없으므로 해당 dp[i]값은 dp[i+1]
• 만약 i일에 상담을 시작하는 게 가능하면, i일에 상담을 하는 경우와 상담을 하지 않는 경우 중 비용이 큰 값으로 선택해서 dp[i]을 갱신한다.

 

💻 소스코드

# 퇴사 - BOJ 14501
# DP
n = int(input())

t = []
p = []
dp = [0] * (n+1)

for _ in range(n):
    a, b = map(int, input().split())
    t.append(a)
    p.append(b)

for i in range(n-1, -1, -1):
    # i일에 상담을 하는 것이 퇴사 날짜 넘음
    if i + t[i] > n:
        dp[i] = dp[i+1]
    else:
        # i일에 상담을 하지 않는 경우와 상담을 하는 경우 중 비용이 큰 값으로 선택
        dp[i] = max(dp[i+t[i]]+p[i], dp[i+1])

print(dp[0])