5. 바둑이 승차 - Cut Edge Tech

바둑이 승차(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

 

문제풀이

#섹션2의 대표값과 유사 - 평균과 가장가까운 것

import sys
sys.stdin=open("input.txt", "r")
from collections import deque

def DFS(L, sum, tsum):   #L은 인덱스 또는 레벨을 의미  
  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
  for i in range(N):
    a[i] = int(input())
  result = -214700000
  total =sum(a)
  DFS(0,0,0)
  print(result)

 

 

해설

★전위순회, 중위순회, 후위순회이든 간에 모두 이 잡듯이 샅샅이 전부 탐색한다.

 

★변수 C 의 DFS함수에서 할당을 하지 않았으므로 DFS함수의 로컬변수가 되지 않고, 여전히 전역변수이다

 

★total: 바둑이들의 전체 무게의 합

 

★tsum: 판단한(과거) 바둑이들의 일부 무게의 합

 

★total - tsum 의 의미: 앞으로 추가적으로 판단해야할 바둑이들의 무게의 합(미래)

 

★sum의 의미: 내가 지금 계산하고 있는 부분집합의 합(현재시점)

 

★sum +(total -tsum) 의미:

 ▶내가 지금 계산하고 있는 바둑이들 무게의 부분집합의 합(현재시점) +

                                                                 앞으로 추가적으로 판단해야 할 바둑이들의 무게의 합(미래)

 

 ▶나 자신(현재 부분집합의 합) + 앞으로 뻗어나갈 자식의 합 (통짜바리)