[백준] 14501번(퇴사)

백준 14501번

최종 제출 코드

n = int(input())
array = [list(map(int, input().split())) for i in range(n)]

stack = []
max_value = 0

def dfs(index):
  
  global max_value
  max_value = max(max_value, sum(stack))
  
  for i in range(index, n):
    # i<n은 검사하지 않아도 무관
    if i < n and i+array[i][0] <= n:
      stack.append(array[i][1])
      dfs(i+array[i][0])
      stack.pop()

dfs(0)
print(max_value)

◼ 조합문제와 유사

• 반복문의 범위와 조건검사가 관건(이 부분에서 자꾸 실수를 해서 시간이 오래 걸림)
• 현재 가리키는 원소가 stack에 추가되려면
  ① 그 원소의 인덱스가 array 인덱스 내에 속해야 한다.
  ② 그 원소의 인덱스+걸리는 시간의 값이 n(입력값의 개수)이하여야 한다.