[백준 1450번] 냅색문제 (Python3)

import sys
input = sys.stdin.readline
from bisect import bisect_right

N,C = map(int,input().split())

data = [*map(int,input().split())]

weight0 = data[:N//2]
weight1 = data[N//2:]

sum0 = []
sum1 = []

weight,sum = [weight0,weight1],[sum0,sum1]

def DFS(s,last,i):
  for n in range(last+1,len(weight[i])):
    s += weight[i][n]
    sum[i].append(s)
    DFS(s,n,i)
    s -= weight[i][n]

DFS(0,-1,0)
DFS(0,-1,1)

sum0.append(0)
sum1.append(0)

sum1.sort()

result = 0
for w in sum0:
  result += bisect_right(sum1,C-w)

print(result)

 

부분수열의 합[백준 1208번] 부분수열의 합 2 (Python3) (tistory.com)과 풀이방식이 완전히 똑같은 문제.

오히려 0일때를 고려 안해줘도 돼서 사아알짝 더 쉽다.

 

 

오늘의 교훈) 중간에서 만나기는 유용하다