[백준] 퇴사

풀이

작은 문제의 계산 결과를 재사용하여 큰 문제의 결과를 구할 수 있으므로 동적 프로그래밍을 이용하여 풀 수 있다. 

특정 날짜에서 받을 수 있는 비용의 최댓값은 그 이전 날짜 중에서 받을 수 있는 비용의 최댓값에 현재 날짜의 비용을 더한 값이 될 수 있다. 단 주의해야 할 점은 '상담을 하는데 필요한 기간은 1일보다 클 수 있기 때문에, 모든 상담을 할 수는 없다.'라는 제약사항을 고려해야 한다. 따라서 특정 날짜에서 받을 수 있는 비용의 최댓값을 구하기 위해서는 이전 날짜 중에서 최댓값을 더하되, 이전 날짜의 상담이 특정 날짜에는 종료되어 있어야 한다.

---

코드

import sys 

# 입력 읽기
n = int(sys.stdin.readline())
t, p, dp = [0 for _ in range(n)], [0 for _ in range(n)], [0 for _ in range(n)]
for i in range(n):
    line = sys.stdin.readline()
    line = line.split()
    t[i], p[i] = int(line[0]), int(line[1])

#동적 프로그래밍으로 최댓값 계산
for i in range(n):
    if i + t[i] <= n:
        dp[i], curMax = p[i], p[i]
        for j in range(0, i): 
            if j+t[j] <= i:
                curMax = max(curMax, dp[i]+dp[j])
        dp[i] = curMax
        
print(max(dp))

---

백준 제출 결과

---

출처

www.acmicpc.net/problem/14501