728x90
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)
반응형
'스터디 > 알고리즘스터디-알까기🎯' 카테고리의 다른 글
그리디_회의실 배정, 씨름선수, 창고 정리, 침몰하는 타이타닉, 증가순열만들기, 역수열 (0) | 2022.09.03 |
---|---|
이분탐색_ 이분탐색,랜선자르기,뮤직비디오,마구간 정하기 (0) | 2022.09.02 |
냅색 알고리즘 _ 가방문제, 동전교환, 최대 점수 구하기 (0) | 2022.09.02 |
[7]알고리즘스터디 - 섹션7_3주차 스터디 (0) | 2022.02.28 |
[6]알고리즘스터디 - 섹션6_3주차 스터디 (0) | 2022.02.28 |