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

문제

전형적인 DFS. 부분집합 문제
해당 문제는 포함한다, 포함하지 않는다의 기준으로 문제를 풀면 바로 풀린다.

-> 그리고 현재가 되지 않는 경우라면 포함하지 않던 시점으로 백트랙킹(원상복구) 후 다시 진행

내 코드

import sys
sys.stdin = open("input.txt", "rt")

def DFS(L, length):
    global res
    if L == n: # 모든 인덱스 확인 종료조건
        if length >= B and length < res:
            res = length
    else:
        DFS(L+1, length + data[L]) # 현재 탑 추가
        DFS(L+1, length) # 현재 탑 추가하지 않음
T = int(input())
for t in range(1,T+1):
    n,B = map(int, input().split())
    data = list(map(int, input().split())) # 탑 각각의 높이
    # B이상인 것 중 가장 작아야함.
    res = int(1e9)
    DFS(0,0)

    print(f"#{t} {res-B}")

문제 해결

탑의 높이가 B이상인 경우 선반 위의 물건을 사용할 수 있는데, 탑의 높이가 높을수록 더 위험하므로 높이가 B이상인 탑 중에서 높이가 가장 낮은 탑을 알아내려고 한다.
-> 이 부분을 보고 모든 경우 중에 B이상인 것들 중 가장 낮은 탑 찾아야 한다고 인식
-> 부분집합으로 모든 경우 확인 후 계산하면 됐다.