[DP/동적계획법] 백준 15486 퇴사 2 - 파이썬(Python)

 

[ Contents ]

 

 

1. 문제 (링크 참조)

15486번: 퇴사 2

 

 

 

2. 문제 풀이

 작업 스케줄이 주어집니다. 작업 시작일과 걸리는 일 수, 수익을 고려해서 최대 수익을 계산해야 합니다.

 

 

2022.05.30 - [Algorithm] - [DP/동적계획법] 백준 14501 퇴사 - 파이썬(Python)

 퇴사 1과 달리, 일 수가 15가 아니라 1,500,000입니다. 상당히 크므로 그리디가 아닌 DP로만 풀 수 있습니다. 풀이 방법은 위 글에서 참조하실 수 있습니다.

 

 

 

3. 코드

import sys
input = sys.stdin.readline

# 입력
N = int(input())
consulting = []
for _ in range(N):
    consulting.append(list(map(int, input().split())))  # 시간, 가격

# DP
day = [0] * (N + 1)  # 해당 날짜에 최대로 받을 수 있는 돈
for i in range(N - 1, -1, -1):  # 마지막 날부터 첫 날까지 거슬러서 계산
    # N일을 벗어나는 스케줄은 무시
    if i + consulting[i][0] > N:
        day[i] = day[i + 1]

    # 해당 스케줄을 함으로써 더 돈을 많이 벌면 갱신
    else:
        day[i] = max(day[i + 1], day[i + consulting[i][0]] + consulting[i][1])
print(day[0])