DP - 퇴사

jisu_log·2025년 4월 5일

알고리즘 문제풀이

목록 보기
13/105

n = int(input())

sc_list = []
dp_list = [0] * (n + 1)
# dp_list[i] : i번째 날부터 마지막날까지 얻을 수 있는 최대 이익

for i in range(0, n):
    line = list(map(int, input().split()))
    sc_list.append(line)

# 뒤에서부터 시작해서 차근차근 최적해를 저장 (n-1 ~ 0까지)
for i in range(n - 1, -1, -1):
    t, p = sc_list[i]  # t: 상담 소요기간, p: 상담으로 벌 수 있는 이익

    if i + t <= n:  # 오늘 상담을 퇴사 당일까지 끝낼 수 있다면
        # 오늘 상담을 진행하는 경우 / 진행하지 않을 경우 중 더 큰 이익을 저장
        dp_list[i] = max(dp_list[i + t] + p, dp_list[i + 1])

    else:  # 오늘 상담은 기간상 진행이 불가하다면
        # 오늘 쉬고 다음날부터 얻을 수 있는 최대 이익을 저장
        dp_list[i] = dp_list[i + 1]
print(dp_list[0])

0개의 댓글