N,S=map(int,input().split())
nums=list(map(int,input().split()))
nums2=nums[0:int(N/2)]
nums3=nums[int(N/2):int(N+1)]
result={}
l=0
r=0
total=0
def reculse(count,sum):
if count==len(nums2):
result[sum]=result.get(sum,0)+1
return
reculse(count+1,sum)
reculse(count+1,sum=sum+nums2[count])
def reculse2(count,sum):
global total
if count==len(nums3):
total+=result.get(S-sum,0)
return
reculse2(count+1,sum)
reculse2(count+1,sum=sum+nums3[count])
reculse(0,0)
reculse2(0,0)
if S==0:
print(total-1)
else:
print(total)
https://blog.naver.com/kks227/221382873753
이거 보고 한건데
S-sum 들어가는 모든 게 이해가 안됨.
배열을 나누고 두 배열의 합끼리 다 더해보는 걸
result[sum]=result.get(sum,0)+1
total+=result.get(S-sum,0)
이친구들이 해주는 거 잖음.
그 원리를 모르겠음
이렇게 구현할 수가 있습니다.집합의 크기가 N이라 해 봅시다. 편의상 N은 짝수라고 해 봅시다.그럼 앞쪽 N/2만큼과 뒤쪽 N/2만큼으로 영역을 나눈 후, 각각 L, R 집합이라 명명해보죠.이제 DFS를 해서 깊이 N/2까지 전부 탐색을 합니다. 깊이가 고정되어 있다면 BFS로 하거나 DFS로 하거나 별 차이는 없지만, 이런 류의 문제는 DFS가 구현하기 편합니다.이제 dfs1 함수로 L 안의 가능한 모든 부분집합을 시도해 보고, cnt 맵을 채웁니다. dfs1 함수가 전부 끝나면 cnt[sum]은 L의 부분집합 중 합이 sum인 것의 개수가 됩니다.다음, dfs2 함수를 실행합니다. 끝에 도달할 때마다 현재 얻은 부분집합의 합이 sum일 때 cnt[S-sum]만큼 결과에 더하면 됩니다.
이렇게 할 경우, k 값을 고정해놓고 볼 때 R에서 합이 k인 부분집합의 개수만큼 dfs2 함수의 끝에서 sum이 k가 되고, 그때마다 cnt[S-k]만큼을 결과에 더하므로 결과적으로 결과엔 cnt[S-k]*(합이 k인 R의 부분집합의 개수)만큼이 더해지게 됩니다. 이걸 모든 R의 부분집합에 대해 실행하면 온전한 결과를 얻을 수 있습니다. [출처] 밋 인 더 미들(Meet in the Middle) (수정: 2018-10-25)|작성자 라이
sum일 때 cnt[S-sum]만큼 결과에 더하면 됩니다 = 이게 어떻게 결과가 되는거지?
풀어 써놨는데도 이해가 안가누 ㅠㅠ
고민좀 더해보셈