[알고리즘] 바둑이 승차(DFS)

(문제) 바둑이 승차(DFS)

---

철수는 그의 바둑이들을 데리고 시장에 가려고 한다.

그런데 그의 트럭은 C킬로그램 넘게 태울수가 없다.

철수는 C를 넘지 않으면서 그의 바둑이들을 가장 무겁게 태우고 싶다.

N마리의 바둑이와 각 바둑이의 무게 W가 주어지면, 철수가 트럭에 태울 수 있는 가장 무거운 무게를 구하는 프로그램을 작성하세요.

입력설명

첫 번째 줄에 자연수 C(1<=C<=100,000,000)와 N(1<=N<=30)이 주어집니다.

둘째 줄부터 N마리 바둑이의 무게가 주어진다.

출력설명

첫 번째 줄에 가장 무거운 무게를 출력한다.

테스트케이스

입력예제	출력예제
259 5 81 58 42 33 61	242
4000 16 27 303 251 121 50 55 123 93 360 84 353 429 765 391 562 77	3994
100000000 21 27 567 999 234 50 567 123 4734 754 84 35 1353 76 464 4634 65 89 3553 59 38 4135	22640

---

해결방법

dfs를 통해서 상태 트리를 이용하여, 리스트에 있는 값을 각각 부분집합으로 더하고 해당 더한 값이 지정한 트럭이 태우는 최대 무게 _max 보다 클 경우로 조건을 끊어서 값을 구한다.

하지만 이럴 경우 리스트의 원소가 많아지면 많아질수록 찾아야하는 부분집합이 너무 많아져서 시간이 오래 걸린다.

이것을 해결하기 위해서 처음 리스트 안에 있는 모든 원소를 더한 값을 total 변수로 만들어서 값을 할당하고, 재귀적으로 함수를 접근할 때, total의 값에서 지금까지 들어온 node의 합들을 total에서 뺀다.

그럴 경우 total - sum_max(node를 거치면서 해당 값을 무조건 더하는 변수) + sum_current(지금까지 부분집합 적으로 더한 값을 저장한 변수)를 한다.

이럴 경우 결과로는 밑에 있는 node들을 보지 않아도 전부다 더해지는 값을 알 수 있기 때문에 만약 기존에 저장한 _max 보다 작을 경우는 return을 하여 넘긴다.

동작 시각화

---

코드

# 시간이 너무 걸리기 때문에 timelimit를 나지 않게 하기 위해서 다른 조건을 추가
# 하나의 매개변수를 더 만들어 값을 계속 더하는 것으로 만든다.
def dfs(x, sum_max, sum_current):
    global result_max
    # dfs를 도는 도중에 무게를 넘었을 경우 빠져나온다
    if _max < sum_max:
        return
    # 전체는 알 수 있기 때문에 값이 지금의 result_max 보다 작을 경우 굳이 갈 필요가 없다.
    if result_max > total - sum_current + sum_max:
        return
    if x == len(a)+1:
        if _max >= sum_max:
            if result_max < sum_max:
                result_max = sum_max
    else:
        dfs(x+1, sum_max + a[x-1], sum_current+a[x-1])
        dfs(x+1, sum_max, sum_current+a[x-1])

_max, n = map(int, input().split())

a = [int(input()) for _ in range(n)]
ch = [0] * len(a)

total = sum(a)
result_max = 0

dfs(1, 0, 0)

print(result_max)