[백준/Python] 14501번 - 퇴사

풀이

import sys
n = int(sys.stdin.readline())
board = [[] for _ in range(n)]
# board = [[3, 10], [5, 20], [1, 10], [1, 20], [2, 15], [4, 40], [2, 200]]
for i in range(n):
  board[i] = list(map(int,sys.stdin.readline().split()))

# DP 사용
dp = [0 for i in range(n+1)]
for i in range(n-1,-1,-1):
  if i + board[i][0] > n:
      dp[i] = dp[i+1]
  else:
      dp[i] = max(board[i][1] + dp[i + board[i][0]], dp[i+1])
  
print(dp[0])

DP 사용 - 큰 문제를 작은 문제로 나누어서 해결하는 방법

sys.stdin.readline()

• 파이썬 내장함수인 input보다 빠르게 값을 입력받기 위해 사용

dp = [0 for i in range(n+1)]

• DP의 각 원소는 해당 날짜 (index)에서부터 퇴사날까지 받을 수 있는 최대 이익
• 뒤에서부터 접근할때 , index가 n-1로 시작할 때 list index out of range가 나지 않고 dp[i+1]을 참조할 수 있기 위해서
• n+1일은 퇴사일을 넘기 때문에, 이 날부터 퇴사일까지 받을 수 있는 최대 보수는 0이다. (dp[N+1])

for i in range(N-1,-1,-1):

• 퇴사일을 넘지 않도록 뒤에서 부터 접근

반복문을 돌 때는 두가지 선택권

1. 그 날 일을 안하고 건너뛰는 것

• if i + board[i][0] > n: 오늘 날짜 + 상담을 완료하는데 걸리는 시간 > 퇴사일
• 이 경우 ,그 날의 보수인 (board[i][1])를 챙기지 못함
• 대신, 그 날 일을 안했다고해서 dp[i]에 0을 넣는것이 아니라, 이전까지 일해서 받을 수 있던 최댓값인 dp[i+1] 넣어야 함 (즉, 현상유지)

2. 그 날 일을 하는 것

• 그 날의 보수 (board[i][1]) + 그 날로부터 상담 시간 이후로 넘어간 날에서 가질 수 있는 최대 보수를 dp[i+board[i][0]] 을 더해주는 것
• 일을 안했을 때 최대 보수 dp[i+1] 와 비교하여 큰 값을 dp[i]

board = [[1, 1], [1, 2], [1, 3], [1, 4], [1, 5], [1, 6], [1, 7], [1, 8], [1, 9], [1, 10]]
# i, dp
9 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
8 [0, 0, 0, 0, 0, 0, 0, 0, 0, 10, 0]
7 [0, 0, 0, 0, 0, 0, 0, 0, 19, 10, 0]
6 [0, 0, 0, 0, 0, 0, 0, 27, 19, 10, 0]
5 [0, 0, 0, 0, 0, 0, 34, 27, 19, 10, 0]
4 [0, 0, 0, 0, 0, 40, 34, 27, 19, 10, 0]
3 [0, 0, 0, 0, 45, 40, 34, 27, 19, 10, 0]
2 [0, 0, 0, 49, 45, 40, 34, 27, 19, 10, 0]
1 [0, 0, 52, 49, 45, 40, 34, 27, 19, 10, 0]
0 [0, 54, 52, 49, 45, 40, 34, 27, 19, 10, 0]