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

• 문제 : 장훈이의 높은 선반
• 난이도 : D4
• 언어 : Python
• 문제 링크 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV2b7Yf6ABcBBASw&categoryId=AV2b7Yf6ABcBBASw&categoryType=CODE&problemTitle=1486&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1&&&&&&&&&

def bfs(n, ssum):
    global ans
    
    if ssum >= B + ans:
        return ans
    
    if n == N:
        if ssum >= B and ssum - B < ans:
            ans = ssum - B
        return

    bfs(n + 1, ssum)
    bfs(n + 1, ssum + arr[n])
    return ans


T = int(input())
for tc in range(1, T + 1):
    N, B = map(int, input().split())
    arr = list(map(int, input().split()))
    ans = 12345678
    print('#{} {}'.format(tc, bfs(0, 0)))

가능한 모든 경우의 수를 다 조사하는 방식의 dfs를 활용한다. 직원의 키 리스트를 더한 값, 더하지 않은 값을 각각 재귀함수를 통해 모든 경우의 수를 조사한다.

 

3~4번째 줄의 if문은 가지치기 방식으로 시간을 좀 더 효율적으로 쓸 수 있다.

ssum이 이미 ans(책장 높이와 직원 키의 차이) + B(책장 높이) 보다 크거나 같다면 더 이상 조사 할 필요가 없으므로 리턴해줌