휴가(DFS)

인프런 김태원님의 파이썬 알고리즘 문제풀이를 듣고 작성한 글입니다.

https://inf.run/7EX2

파이썬 알고리즘 문제풀이 (코딩테스트 대비) - 인프런 | 강의

강의 풀이

#강의 풀이
def DFS(L, sum):
    global res
    if L == n+1:
        if sum > res:
            res = sum
    else:
        if L+T[L] <= n+1:
            DFS(L+T[L], sum+P[L])
        DFS(L+1, sum)

if __name__ == "__main__":
    n = int(input())
    T = list()
    P = list()
    for i in range(n):
        a, b = map(int, input().split())
        T.append(a)
        P.append(b)
    res = -2147000000
    T.insert(0, 0)
    P.insert(0, 0)
    DFS(1, 0)
    print(res)

T는 상담시 걸리는 일수이고

P는 상담시 받을수 있는 액수이다.

인덱스로 편하게 사용하기 위해 각각 맨 앞자리에 0을 추가한다.

 

DFS에서 L(level)이 8에 도달하면 retrun하고

sum 값의 최댓값을 결과 res에 저장한다.

 

else에서 DFS는 상담을 하는 것과 안하는것 두갈래로 나눈다.

만약 L + T[L]이 8일 안에 들어간다면 상담을 하고

아니라면 안하는 것으로 DFS  재귀를 돌린다.