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

dfs로 백트래킹하며 최솟값을 갱신해주는 로직입니다. 높이가 '이상' 임이 명확히 주어져있어서 수월했습니다.

 

def dfs(u, total):
    global min_val
    if total >= B:
        min_val = min(min_val, total)
    for v in range(u + 1, N):
        if not visited[v] and total + s[v] < min_val:
            visited[v] = True
            dfs(v, total + s[v])
            visited[v] = False


for test in range(1, int(input()) + 1):
    N, B = map(int, input().split())
    s = list(map(int, input().split()))
    visited = [False] * N
    min_val = float('inf')
    for start in range(N):
        visited[start] = True
        dfs(start, s[start])
        visited[start] = False
    print(f'#{test} {min_val - B}')