[백준] 14501. 퇴사 - Python

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

14501번: 퇴사

---

• 생각
  
  • DP
  • 거꾸로 확인
    • 근무 마지막날부터
  • 해당 상담을 진행 시 근무 종료 전까지 마무리 가능한 경우
    • 상담을 진행
    • 상담을 진행하지 않음
  • 해당 상담을 진행 시 근무 종료 전까지 마무리가 불가능한 경우
    • 다음 날 이익이랑 같음
• 코드

from sys import stdin
input = stdin.readline

# 근무 일
N = int(input())
# 상담 [걸리는 시간, 받을 수 있는 금액]
counsel = [list(map(int,input().split())) for _ in range(N)]

# 각 근무일까지 얻을 수 있는 최대 이익
dp = [0 for _ in range(N+1)]

for day in range(N-1,-1,-1):
    # 해당 일의 상담을 근무 종료 전 마무리 가능한 경우
    if day + counsel[day][0] <= N:
        # 근무를 하는 경우 / 근무를 하지 않는 경우 중 최대 이익이 나는 것 고르기
        dp[day] = max(dp[day+1],dp[day+counsel[day][0]] + counsel[day][1])
    # 해당 일의 상담을 근무 종료 전 마무리 불가능 한 경우
    else:
        dp[day] = dp[day+1]

print(dp[0])