[Python 알고리즘] 장훈이의 높은 선반 - SWEA

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

---

문제 분석

target 이상이면서 가장 작은 조합을 구하고, 조합의 합과 target의 차이를 return 하라.

 

접근

N = 20이므로, 백트래킹으로 풀이하면 2 ** 20 ~= 1,000,000 정도일 것이다.
총합이 target 이상이 되면, target과의 차이를 현재 result 값과 비교하여 갱신한다.

 

모든 원소에 대하여 (추가하거나 / 추가하지 않거나)의 경우를 고려하고, 모든 원소를 탐색하면 result를 갱신한다.

 

코드

def solve(i, total):
    global n, target, res

    if i == n:
        if total >= target:
            res = min(res, total - target)
        return

    solve(i + 1, total + heights[i])
    solve(i + 1, total)


T = int(input())
for tc in range(T):
    n, target = map(int, input().split())
    heights = list(map(int, input().split()))
    res = 1e9
    solve(0, 0)
    print(f'#{tc + 1} {res}')

 

간단한 코드이지만, 2 * n개의 경우의 수를 고려하는 백트래킹 문제의 뼈대 코드인 듯하다.