[python] SWEA : 장훈이의 높은 선반 (backtracking)

1. dfs 사용 

# B 이상인 height 중에서 가장 작은 height 구하기
def backtracking(N, B, height, idx):
    global result
    # 마지막 원소까지 더해버렸다면
    if idx >= N:
        # 선반의 높이 이상이고 최소값보다 작을때 갱신
        if B <= height < result:
            result = height
        return
    visited[idx] = True
    backtracking(N, B, employees[idx]+height, idx+1)
    visited[idx] = False
    backtracking(N, B, height, idx+1)

for tc in range(1, int(input())+1):
    result = 1e9
    n, b = map(int, input().split())
    # 직원들의 키
    employees = list(map(int, input().split()))
    # 방문처리
    visited = [False for _ in range(n)]
    backtracking(n, b, 0, 0)
    print(f'#{tc} {result-b}')