파이썬 알고리즘-46 (DFS/BFS) 바둑이 승차

46.바둑이 승차(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(v,sum,largest):
    if sum>c:
        return
    if v==n:
        print(largest)
    else:
        if sum>largest:
            largest=sum
        dfs(v+1,sum+dogs[v],largest)
        dfs(v+1,sum,largest)

c,n=map(int,input().split())
dogs=[int(input()) for _ in range(n)]
dogs.sort(reverse=True)

dfs(0,0,0)

논리 전개는 초반에 비슷했는데 합을 처리하는 방법에서 무한루프가 떴고, 전역변수 사용하는 법도 제대로 몰랐다.

풀이

def DFS(L, sum, tsum):
    global result
    if sum+(total-tsum)<result:
        return
    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])


if __name__=="__main__":
    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)

반성점

• 전역변수/지역변수의 개념에 대해 알고는 있으나 실제로 활용하지 못함
• 빠르게 동작하는 코드에 대한 생각이 없음

배운 것

• 전역변수와 지역변수
  전역변수는 기본적으로 모든 함수에서 접근할 수 있다. 함수가 실행되고 변수가 존재하면, 함수는 우선 그 변수가 지역변수인가를 확인하고 지역변수가 아니라면 전역변수 목록을 탐색하게 된다. 만약 지역변수에 전역변수가 같은 이름의 변수가 존재한다면, 함수는 지역변수의 값을 사용하게 된다. 전역변수를 그대로 사용하고 싶다면 함수 안에서 global 변수명을 선언해야 한다. 다만 global을 사용해서 전역변수의 값을 함수 안에서 바꿨다면, 함수 밖의 scope에서도 변수의 값이 동일하게 바뀐다.
  한편, 전역에 선언된 리스트의 값을 함수 안에서 바꿀 때(lst[index]=n 등)는 변수를 선언한 것이 아니므로 에러가 나지 않는다. 다만 함수 안에서 전역 리스트와 같은 이름의 리스트를 선언하면(lst=lst+[n]) 새로운 지역변수를 선언한 것과 같으므로 미리 지역변수를 선언하거나 global을 사용하지 않으면 에러가 난다.