[SWEA 1486] 파이썬 - 장훈이의 높은 선반

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

SW Expert Academy

 

# 조건

• 높이가 B인 선반과 N명의 점원
• 각 점원들의 키는 Hi 고 (1<=H<=10000)
• 각 점원들이 선반위의 물건을 꺼내기 위해 탑을 쌓는데 탑은 최소 1명의 점원으로 이루어져있다.
• 선반 B보다 높은 탑 중 가장 낮은 탑과의 차이를 구하여라

 

# 접근 방법

• 부분 집합을 구해주면 될 것 같기 때문에 순열과 조합 중에 선택하면 된다.
• N이 20정도가 되면 A+B와 B+A는 같기 때문에 순서가 상관없는 조합으로 구해준다.
• 조합의 원소수가 1개에서부터 N개까지를 반복문 변수 i를 통하여 변경시켜준다.

 

from itertools import combinations
import sys
sys.stdin = open('input.txt')

# 높이 B인 선반, N명의 점원들의 키는 Hi
# 탑을 쌓아서 키보다 높이 있는 물건 꺼낼수 있다.
# 높이가 b이상 중 가장 낮은 탑의 높이와 b의 차이

T = int(input())
for tc in range(1, T+1):
    N, B = map(int, input().split())
    a = list(map(int, input().split()))
    # 나올수 없는 제일 큰수를 min값으로 잡아준다.
    result = 200001
    for i in range(1, N+1):
        # 1~N개로 이루어진 조합을 person에 담아주며
        person = list(combinations(a, i))

        for j in person:
            # 문제 조건의 B보다 조합의 합이 크다면
            if sum(j) >= B:
                # 그때의 차이가 min값 보다 작다면 재설정해준다.
                if sum(j)-B < result:
                    result = sum(j)-B

    print(f'#{tc} {result}')