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

📕 문제

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV2b7Yf6ABcBBASw 

SW Expert Academy

 

💡 풀이법

: 그냥 단순한 조합 문제였다.

 

1. 키 리스트를 오름차순 정렬시켜준다.

2. 답을 담을 ans를 +무한대로 초기화시켜준다.

3. n은 직원의 수이다. 1부터 N까지 while문을 돌며 1씩 증가시켜준다.

4. 실행시간을 단축하기위해 먼저 직원의 수가 n일때의 가장 높은 탑의 높이를 B와 비교해서 작다면 바로 continue를 해서 아래를 실행시키지 않고 n을 1 증가시켜줬다.

5. 조합의 합은 s인데 s가 B보다 클때, 현재 ans보다 s가 더 작다면 ans를 s로 바꿔준다.

 

from itertools import combinations

T = int(input())
for tc in range(1, T + 1):
    N, B = map(int, input().split())
    talls = list(map(int, input().split()))
    talls.sort()
    n = 0
    ans = float('inf')
    while n <= N:
        n += 1
        if sum(talls[N-n:]) < B:
            continue
        for item in combinations(talls, n):
            s = sum(item)
            if s >= B and s < ans:
                ans = s
    print('#{} {}'.format(tc, ans-B))