[python] 바둑이 승차(DFS)

[문제]

철수는 그의 바둑이들을 데리고 시장에 가려고 한다. 그런데 그의 트럭은 C킬로그램 넘게 태울수가 없다.
철수는 C를 넘지 않으면서 그의 바둑이들을 가장 무겁게 태우고 싶다.
N마리의 바둑이와 각 바둑이의 무게 W가 주어지면, 철수가 트럭에 태울 수 있는 가장 무거운 무게를 구하는 프로그램을 작성하세요.

▣ 입력설명
첫 번째 줄에 자연수 C(1<=C<=100,000,000)와 N(1<=N<=30)이 주어집니다.
둘째 줄부터 N마리 바둑이의 무게가 주어진다.

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

▣ 입력예제 1
259 5
81
58
42
33
61

▣ 출력예제 1
242

---

[풀이]

def dfs(l, sum, tsum):  # l: 인덱스, sum: 부분집합의 합, tsum: 판단한 부분집합의 합
    global result

    # total-tsum: 앞으로 판단해야 할 바둑이들의 총 무게
    if sum+(total-tsum) < result:     # cut-edge 2번 조건
        return      # 밑으로 가지 뻗을 필요가 없음
    if sum > c:     # cut-edge 1번 조건
        return
    if l == n:  # 종착점. 부분집합 1개 완성
        if sum > result:
            result = sum
    else:
        dfs(l+1, sum+a[l], tsum+a[l])
        dfs(l+1, sum, tsum+a[l])



c, n = map(int, input().split())
a = [0] * n     # 바둑이 각각의 무게
result = -2147000000        # 가장 큰 값을 구해야 하니, 아주 작은 값으로 초기화
for i in range(n):
    a[i] = int(input())
total = sum(a)

dfs(0, 0, 0)
print(result)

---

[내용]

- 처음에 로직 자체를 이해하지 못했었다. 처음 잘못 이해한 로직: 

1. 입력 받은 값들을 내림차순 sort =>
2. 아래 처럼 더한 값들과 c를 비교.  
    1+2
    1+2+3
    1+2+3+4
3. 더한 값 < c => 그 다음 값을 더해봄
4. 더한 값 == c => 이 값 출력
5. 더한 값 > c -> 이 전 값 까지만 더하고 출력 

==========> 이전 문제 처럼 인덱스를 가지고 풀어야 한다. 

 

- 2개 갈래인 상태트리를 만들어 DFS로 풀어야 한다. 여기서 DFS 함수 인자로는 상태트리의 레벨을 가리키는 인덱스(몇 마리를 태울 것인지를 의미)와 실시간으로 누적되는 바둑이들의 무게 합.

- 시간 복잡도 줄이기: Cut-edge 조건 추가!! ->

① 중간에 누적된 무게 합이 최대 몸무게(C) 보다 커지게 되는 순간 return

② 실시간으로 포함여부에 따라 갱신된 누적 무게 합을 총 제한 무게에서 뺀 값과 현재 탐색하고 있는 갈래 아래의 부분집합들을 모두 합한다고 해도 현재 갱신된 무게 합 보다 작다면 굳이 더 탐색할 필요 없음