[완전탐색][상태 트리] - 최대 점수구하기(DFS)

def DFS(L, s,ts):
    global res
    if ts > m:
        return
    if L == n:
        if res < s:
            res = s
    else:
        DFS(L+1, s + a[L][0], ts + a[L][1])
        DFS(L+1, s, ts)


if __name__ =="__main__":
    n, m = map(int,input().split())
    res = -2174000000
    score = []
    for i in range(n):
        a, b = map(int,input().split())
        score.append([a,b])
    a= sorted(score,key=lambda x:x[1])
    a.sort(reverse=True)
    DFS(0,0,0)
    print(res)

• 상태 트리를 사용해서 풀었다.
• 종료 조건
  • 해당 노드가 n까지 내려갔을 때 현재 값이 최대 값인지를 확인했고 맞다면 res를 현재까지 더한 s 값으로 바꿔주었다.
  • 해당 시간이 초과했다면 더이상 살펴보지 않고 return 시켜준다.