퇴사 [백준 14501번]

문제

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

14501번: 퇴사

 

내 풀이

 

처음에 배열로 다이나믹 프로그래밍을 하려다가, 머리가 안 돌아가서 재귀 함수를 사용하였다.

 

여기서 포인트는 i일을 선택할 것인지 또는 선택하지 않을 것인지 구현하는 것이다.

만약 i일을 선택할 경우, time[i]도 고려해야 한다.

 

import sys
input = sys.stdin.readline

N = int(input())
time, pay = [0], [0]
for i in range(N):
    t, p = map(int, input().split())
    time.append(t); pay.append(p)

MAX = 0
def schedule(i, profit):
    global MAX
    if i > N:
        MAX = max(MAX, profit)
        return
    schedule(i+1, profit)
    if time[i] <= N-i+1:
        schedule(i+time[i], profit+pay[i])
    
schedule(1, 0)
print(MAX)

 

총평

다이나믹 프로그래밍 너무 오랜만에 해봐서 버벅거렸지만 그래도 해냈다.