완전탐색_바둑이 승차_cut edge 방법,DFS 시간초과를 방지하는 법

 

if  ans > val + ( total - tsum )  : return

 

전체 합에서 tsum(바둑이를 태웠건 안태웠건 지나간 바둑이의 무게) 을 빼면

앞으로  더할 수 있는 바둑이의 무게가 나온다.

여기서 val을 더한 값이 ans보다 작다면 더 할 필요가 없다. 

끝까지 가도 어차피 ans보다 작기 때문이다. 

 

 

 

dfs에 tsum을 인수로 추가하여 시간 초과를 막는다는 것이 흥미롭다. 

 

 

def dfs(idx,val,tsum) :
    global ans 
    if val > c : return 
    if ans > val + (total-tsum) : return 
    if idx == n : 
        ans = max(ans,val) 
        return 
    else :
        dfs(idx+1,val+arr[idx],tsum+arr[idx])
        dfs(idx+1, val ,tsum+arr[idx])
    
if __name__=="__main__" :
    c,n = map(int,input().split())
    arr = [int(input()) for _ in range(n)]
    total = sum(arr)
    ans = 0
    dfs(0,0,0)
    print(ans)