6.5 바둑이 승차(DFS)

 

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

    if v==n:
        sum=0
        for j in range(n):
            if ch[j]==1:
                sum+=weight_list[j]
        if sum<=c:
            result_list.append(sum)
              
    else:
        ch[v]=0
        DFS(v+1)
        ch[v]=1
        DFS(v+1)

if __name__=="__main__":
    result_list=[]
    weight_list=[]
    c, n=map(int, input().split())
    for i in range(n):
        a=int(input())
        weight_list.append(a)
    ch=[0]*n
    DFS(0)
    print(max(result_list))

-경우의 수를 나누는 방법에 체크 리스트 사용

체크 리스트의 0과 1로 부분 집합에 포함 여부를 결정해서 경우의 수를 나누어서 합계를 따로 구했음

 

-합계 리스트를 따로 작성하여 통과한 합계들을 리스트에 추가하여

그 리스트의 최댓값을 출력하는 코드를 작성함

 

-시간 초과 문제점 존재

 

---

강의 풀이

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])

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)

-시간 초과 해결

tsum이란

-->만약 진행 지점까지의 지나온 원소들이 모두 부분집합에 포함되었을 때의 합계이다

total

-->모든 바둑이의 무게의 합

sum

-->진행 지점까지의 부분 집합의 합

if sum+(total-tsum)<result:

        return

 시간 초과를 해결하기 위한 코드

 불필요한 계산을 생략함

 여태까지의 sum(합계)에서 나머지 거쳐야 할 바둑이의 무게들이 모두 포함된다고 가정하고 더해도 

 result값보다 작다면 당연히 result값이 아직까지 답이므로 계산을 할 필요가 없다

--> 시간 초과 해결

 

-global 전역 변수로 이용

나의 방식과 다르게 result 변수를 선언하고 큰 값이 나올 때마다 result 값을 초기화함

그리고 그 result값을 함수 내에서 다시 이용하기 위해

함수 첫줄에 

global result

코드 작성해서 처리함

 

-부분 집합 하나 완성시 처리

if L==n: 

        if sum>result:

            result=sum

L==n의 의미는 부분 집합이 하나 완성되었다는 의미이다. 이 때 이전의 result보다 값이 크다면

result가 현재의 부분 집합 합계의 값으로 업데이트된다.