SWEA_1486_장훈이의 높은 선반

아이디어 1

• 부분집합을 따로 구하지 않고, 키를 더한 경우와 더하지 않은 경우를 거쳐가며 탐색한다.

def sub_set(set_idx, num_sum, num_remain_sum):
    global result

    if set_idx == N:
        if num_sum >= H:
            result = min(result, num_sum - H)
        return

    if num_sum + num_remain_sum < H:
        return

    sub_set(set_idx + 1, num_sum + HEIGHTS[set_idx], num_remain_sum - HEIGHTS[set_idx])
    sub_set(set_idx + 1, num_sum, num_remain_sum - HEIGHTS[set_idx])


T = int(input())

for tc in range(1, T + 1):
    N, H = map(int, input().split())
    HEIGHTS = list(map(int, input().split()))

    result = 100000
    sub_set(0, 0, sum(HEIGHTS))
    print(f"#{tc} {result}")

배운 점😉😉

• 부분집합을 구하지 않고, 진행하며 처리할 수 있는 방법도 생각해보기

• 중복된 연산을 하지 않도록 가지치기하는 방법에 대한 고민

# 남은 수를 더하더라도, 기준 값을 넘기지 못한다면 더이상 연산을 수행할 필요가 없다.
if num_sum + num_remain_sum < H:
    return