(Python) 백준 14501번: 퇴사

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

14501번: 퇴사

 

(Python) 백준 14501번: 퇴사¶

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

• 알고리즘 분류:
  • 브루트 포스
  • 다이나믹 프로그래밍

---

In [1]:

def dfs(t, p):
    global maxv
    if t == N+1:
        if maxv < p:
            maxv = p
        return
    ## 일을 하는 경우
    if t + work_array[t-1][0] <= N+1:
        dfs(t + work_array[t-1][0], p + work_array[t-1][1])
    ## 일을 안하는 경우
    dfs(t+1, p)

In [2]:

if __name__ == '__main__':
    N = int(input())
    work_array = [list(map(int, input().split())) for _ in range(N)]
    maxv = 0
    dfs(1, 0)
    print(maxv)

7
3 10
5 20
1 10
1 20
2 15
4 40
2 200
45