[완전탐색][상태 트리] - 휴가(DFS)

풀이

def DFS(L, money, day):
    global res
    if day > n:
        return
    if day == n:
        if res < money:
            res = money
    else:
        DFS(L+1, money + schedule[day][1], day + schedule[day][0])
        DFS(L+1, money, day+1)



if __name__ =="__main__":
    n = int(input())
    schedule = []
    for _ in range(n):
        a, b = map(int,input().split())
        schedule.append([a,b])
    res = -2147000000
    DFS(0,0,0)
    print(res)

---

설명

• schedule.append([a,b]) - schedule[변수][0] = 해당 작업에 걸리는 날짜, [1]번째에는 해당 작업에 대한 보상이 담겨져 있다.
• DFS를 사용해서 상태트리의 누적 작업을 진행한다.
• if day > n: - 해당 상황을 return 해서 함수를 종료시킨다.
  당연하게도 주어진 날짜보다 작업을 진행하는 날짜가 더 길면 안 된다.
• if day == n: - 해당 작업이 주어진 날짜에 달했다면 조건을 확인해준다. 지금까지 더해온 휴가비가 그전에 조건에 부합해서 누적했던 휴가비보다 많다면 res = money 휴가비의 최대 금액을 현재 누적액으로 바꿔준다.
• 종료 조건에 만족하지 않는다면 DFS를 통해 계속 진행한다.
  이때 날짜는 계속해서 확인해주어야 하기에 +1 해준다.
  또한 상태트리로 다음 값을 더해주고 더하지 않고 하는 방식을 사용해 제일 만족하는 값을 찾아간다.