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

 

[ Contents ]

 

 

1. 문제 (링크 참조)

14501번: 퇴사

 

 

 

2. 문제 풀이

 주어진 스케줄 내에서 최대 이익을 구하는 문제입니다.

 

2022.02.12 - [Algorithm] - [Algorithm] 메모해두고 불러와서 사용하는 동적 프로그래밍(DP)

[Algorithm] 메모해두고 불러와서 사용하는 동적 프로그래밍(DP)

 작업 스케줄링 문제입니다. 작업 일정이 고정되어 있기 때문에, 그리디 알고리즘으로는 풀 수가 없습니다. 따라서, DP로 스케쥴을 넣고 빼면서 비교하며 최대 이익을 구합니다.

 

 

 

3. 코드

# 입력
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])

 마지막 날부터 첫 날까지 거슬러서 최대 이익을 계산합니다. 퇴사일(N)이 넘지 않으면, 해당 스케쥴을 넣는 게 나은지 비교 후에 갱신합니다.