[완전탐색][상태 트리] - 바둑이 승차(DFS)

def DFS(L, sum, tsum):
    global result
    if sum+(total-tsum)<result:
        return
    if sum>c:
        return
    if L==n:
        if sum>result:
            result=sum
    else:
        DFS(L+1, sum+a[L], tsum+a[L])
        DFS(L+1, sum, tsum+a[L])


if __name__=="__main__":
    c, n=map(int, input().split())
    a=[int(input()) for _ in range(n)]
    result=-2147000000
    total=sum(a)
    DFS(0, 0, 0)
    print(result)

• 종료 조건을 더 늘려서 속도를 개선했다.
• 해당 res에 들어간 값보다 아래 가지를 더해도 값이 더 가까워지지 않을 땐 res를 사용하도록 하는 것이다.