[인프런] 바둑이 승차

---

문제설명

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

입력조건

• 첫줄에 자연수 C(1 <= C <= 100,000,000(1억)) 와 N(1 <= N <= 30)이 주어진다.
• 둘째 줄부터 N마리 바둑이의 무게가 주어진다.

출력조건

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

사고과정

• 2개 갈래인 상태트리를 만들어 DFS로 해결하면 된다. 단, DFS 함수 인자에는 상태트리의 레벨을 가리키는 인덱스(여기서는 바둑이 몇 마리를 태울 것인지를 의미)와 실시간으로 누적되는 바둑이(들)의 무게 합을 넣어준다.
• 시간 복잡도를 줄기이 위한 Cut-edge 하는 방법으로는 중간에 누적 무게 합이 최대 몸무게(C)보다 커지게되는 순간 return 시켜 그 갈래는 더 탐색하지 않도록 한다.
• 풀이를 보니, 내가 한 Cut-edge 방법 말고도 1개의 추가 Cut-edge 방법을 두어서 새로운 기술을 배웠다. 실시간으로 포함여부에 따라 갱신된 누적 무게 합을 총 제한 무게에서 뺀 값과 현재 탐색하고 있는 갈래 아래의 부분집합들을 모두 합한다고 해도 현재 갱신된 무게 합보다 작다면 굳이 더 탐색할 필요가 없다는 것!

풀이

- 강의 풀이(권장!)

c, n = map(int, input().split())
a = [0] * n   # 바둑이 각 무게를 저장
result = -214700000
for i in range(n):
    a[i] = int(input())
total = sum(a)


def DFS(L, sum, tsum):
    """
    L: 인덱스
    sum: 실시간 부분집합 합(포함 여부에 따라)
    tsum: 포함여부상관없이 실시간 부분집합 합
    """
    global result
    # Cut-edge2 -> 중요!
    if sum + (total - tsum) < result:
        return
    # Cut-edge1
    if sum > c:
        return
    if L == n:
        if sum > result:
            result = sum
    else:
        DFS(L+1, sum + a[L], tsum+a[L])
        DFS(L+1, sum, tsum+a[L])

DFS(0, 0, 0)
print(result)

- 나의 풀이

c, n = map(int, input().split())
arr = [int(input()) for _ in range(n)]
max_val = 0

def dfs(idx, kg):
    global max_val
    # 시간복잡도 줄이기 위한 추가 요건 -> 중간에 더하다가 c보다 커지면 바로 탐색 중단
    if kg > c:
        return
    # 종단 조건
    if idx == n:
        if kg <= c: # 해당 조건 없어오 됨. 위 if kg > c 조건이 어차피 필터링함!
            max_val = max(max_val, kg)
        return
    # DFS
    else:
        dfs(idx+1, kg+arr[idx])  # 해당 인덱스 값을 포함할 경우
        dfs(idx+1, kg)           # 해당 인덱스 값을 포함하지 않을 경우

# 만약 c가 주어진 바둑이 무게 총 합보다 클 경우에는 그냥 바로 sum 반환
if sum(arr) <= c:
    print(sum(arr))
else:
    dfs(0, 0)  # arr의 인덱스, 누적 무게
    print(max_val)