SWEA 1486. 장훈이의 높은 선반(Python)(D4)

주어진 점원들의 키의 합중 B에 가장 가깝고 B보다 크거나 같은 값을 찾는 문제이다.
점원들의 부분집합들을 dfs(백트래킹)을 통해 계산하며, 합이 B와같거나 클경우 합과 결과값중 낮은값으로 계속 갱신해준다!

res=[]
def check(height,vi,idx):
    global B,tmp
    if height>=B:
        tmp=min(tmp,height-B)
        print(vi)
        return
    for i in range(idx,N):
        vi[i]=1
        check(height+li[i],vi,i+1)
        vi[i]=0

for m in range(int(input())):
    tmp=200000 # 최대값, 점원의 키 최대값=10000, 최대점원의 수=10
    N,B=map(int,input().split())
    li=list(map(int,input().split()))
    visit=[0]*(N)
    check(0,visit,0)
    res.append(tmp)
for i in range(len(res)):
    print("#%d %s"%(i+1,res[i]))