[백준 파이썬] 14501 퇴사

14501번: 퇴사

예시처럼 일정표가 있을 때 수익은

• 7일에는 일을 하지 못한다.
• 6일에도 일을 하지 못한다.
• 5일에 시작해서 6일에 끝낸다(15). 7일에 일을 할 수 있다면 한다.
• 4일에 일을 끝낸다(20). 5일 이후에 가능한 일을 한다(15). -> 35
• 3일에 일을 끝낸다(10). 4일 이후에 가능한 일을 한다(35). -> 45
• 2일에 시작해서 6일에 끝낸다(20). 7일에 일을 할 수 있다면 한다.
• 1일에 시작해서 3일에 끝낸다(10). 4일 이후에 가능한 일을 한다(35). -> 45

로 마지막 날부터 계산할 수 있다. i일차의 수익을 dp[i]에 저장할 때 아래와 같이 작성하면 된다.

N = int(input())
schedules = [list(map(int, input().split())) for _ in range(N)]

dp = [0 for _ in range(N+1)]
for i in range(N-1, -1, -1):
	# 현재 날짜와 일하는데 걸리는 날이 전체 날짜보다 크다면
    if i + schedules[i][0] > N:
        dp[i] = dp[i+1] # 오늘은 일 못한다. 내일 수익으로 저장
        continue

	# 내일 수익과, 오늘 수익에 오늘 일정이 끝난 날 이후의 수익을 더한 값을 비교해
    # 오늘까지의 수익으로 저장한다.
    dp[i] = max(dp[i+1], schedules[i][1] + dp[i+schedules[i][0]])

print(dp[0])