20200807 // 삼성 SW Expert 아카데미 문제 // 1486

삼성 SW Expert 아카데미 1486번 "장훈이의 높은 선반" 문제입니다.

from itertools import chain, combinations
TC = int(input())   

def powerset(iterable):
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s) + 1))

ans = []
for tc in range(1, TC + 1):
    k = "#"+str(tc) + " "
    N, B = map(int, input().split())
    lst = list(map(int, input().split()))
    lst1 = list(set(powerset(lst)))
    lst2 = []
    for e in lst1:
        if sum(e) >= B:
            lst2.append(sum(e))
    lst2 = list(set(lst2))
    k += str(min(lst2) - B)
    ans.append(k)
for e in ans:
    print(e)

 

조합과 중복제거를 활용해서 풀었는데 조합은 itertools의 combinations를, 중복제거는 set 자료구조를 이용해서 구했다.

 

받은 입력을 부분집합으로 경우의 수를 구해서 합을 계산, 그 후 set을 이용해서 합의 중복을 제거했다.

 

그리고 부분집합의 합이 B보다 커야 하므로 큰 값들만 리스트에 담아서 그 중 최소값을 구하면 된다.