[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(x,summ):
    global M
    if summ>c:
         return
    if x==n: 
        if summ>M:
                M=summ
    else:
        DFS(x+1,summ+arr[x])
        DFS(x+1,summ)

c,n=map(int,input().split())
arr=[]
for _ in range(n):
    arr.append(int(input()))
M=0
DFS(0,0)
print(M)

처음 이전 부분집합들의 문제처럼 체크 리스트 ch를 사용하려고 했으나 생각해보니 중복된 무게를 가진 바둑이가 나올수 있어 접근을 다르게 했다. 이전 문제와 같이 DFS의 인자로 레벨과 합 두개를 가지게 했다.

 

 

 

 

 

정답 코드

import sys
sys.stdin=open("input.txt", "r")
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)

나의 코드와 거의 비슷하지만 cut-edge기법이 하나가 더 들어갔다.

바로 tsum(부분 집합에 넣든 넣지 않았든 탑색을 했단 무게들의 총합)이다.