[Python Algorithm] 완전탐색(DFS) - 바둑이 승차

> 완전탐색 - 백트랙킹, 상태트리와 CUT EDGE / 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

 

 

import sys

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])
        
        
c, n = map(int, input().split())
a = [0]*n
result = -2147000000
for i in range(n):
	a[i] = int(input())
    
DFS(0, 0, 0)
print(result)

 

 

⭐️ Point ! ⭐️

• global result
  아래 코드에서 result=sum로 정의를 하고 있다. 이렇게 되면 result는 지역변수가 되기 때문에
  우리는 main에서 사용하는 result 전역변수를 사용하기 위해서는 함수 안에 다시 'global'을 사용해서 선언해줘야 한다.
  
  
• 부분 집합으로 구하기 
  
  
• tsum 변수
  이 변수는 이제껏 넣을까 말까 판단한 바둑이들을 제외한 남은 바둑이들의 총합이다.
  그 바둑이들의 총합과 판단하여 구한 sum을 더한 값이 이제껏 최선의 값이라고 판단했던 result값보다 작으면
  굳이 남은 바둑이들을 판단할 필요가 없으므로 시간 단축을 위해 작성된 코드이다.

 

 

 

 

출처

• 인프런 : 파이썬 알고리즘 문제 풀이