[SWEA] 1486 장훈이의 높은 선반 Python

[ 문제 ]

 

난이도:  D4

문제 번호:  1486

 

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV2b7Yf6ABcBBASw&categoryId=AV2b7Yf6ABcBBASw&categoryType=CODE&problemTitle=1486&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1

SW Expert Academy

---

 

장훈이는 서점을 운영하고 있다.

서점에는 높이가 B인 선반이 하나 있는데 장훈이는 키가 매우 크기 때문에, 선반 위의 물건을 자유롭게 사용할 수 있다.

어느 날 장훈이는 자리를 비웠고,

이 서점에 있는 N명의 점원들이 장훈이가 선반 위에 올려놓은 물건을 사용해야 하는 일이 생겼다.

각 점원의 키는 Hi로 나타나는데, 점원들은 탑을 쌓아서 선반 위의 물건을 사용하기로 하였다.

점원들이 쌓는 탑은 점원 1명 이상으로 이루어져 있다.

탑의 높이는 점원이 1명일 경우 그 점원의 키와 같고,

2명 이상일 경우 탑을 만든 모든 점원의 키의 합과 같다.

탑의 높이가 B 이상인 경우 선반 위의 물건을 사용할 수 있는데 탑의 높이가 높을수록 더 위험하므로

높이가 B 이상인 탑 중에서 높이가 가장 낮은 탑을 알아내려고 한다.

for tc in range(1, int(input())+1):
    N, B = map(int, input().split())
    numbers = list(map(int, input().split()))
    min_v = 987654321
 
    for i in range(1 << N):
        total = 0
        for j in range(N):
            if i & (1 << j):
                total += numbers[j]
        if total - B >= 0 and min_v > total - B:
            min_v = total - B
    print('#{} {}'.format(tc, min_v))