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

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV2b7Yf6ABcBBASw 

SW Expert Academy

점원의 탑을(?) 쌓아서 선반보다 높이 쌓았을 때의 크기와 선반의 크기의 차이의 최소값을 구하는 문제

백트래킹을 활용하여 풀 수 있다.

⚙️내가 푼 정답 코드

def backtracking(a, sum_h):
    global result
    if sum_h >= result:  # 지금 하는 합이 결과보다 크면
        return  # 끝
    if sum_h >= B:  # 선반보다 높아
        result = min(result, sum_h)  # sum_h가 더작으면 result에 추가해
        return
    for i in range(a, N):  # 부분 집합을 찾아보자
        backtracking(i+1, sum_h + height[i])

T = int(input())
for case in range(1, T + 1):
    N, B = map(int, input().split())
    height = list(map(int, input().split()))
    result = float('inf')
    backtracking(0,0)
    print(f'#{case} {result - B}')

반응형

📌문제 접근 포인트

1. 부분 집합의 합 문제와 동일한 형태의 문제로, 모든 부분집합의 합을 구하고 그거와 선반의 크기를 비교하면 되는 간단한 문제이다.
2. 부분집합을 구하기 위한 백트래킹을 구성 후, 선반의 높이와 비교해주자
3. 부분집합의 합과 선반의 높이의 차이 중에서 제일 작은 것을 출력하면