파이썬 알고리즘 046 | 바둑이 승차(DFS)-Cut Edge Tech

Yunny.Log ·2021년 1월 15일

Algorithm

목록 보기

46/318

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

<내 풀이>

앞에서 한 것처럼 부분합을 구하고 sum도 구한다, sum이 c를 안 넘을 때까지

def DFS(L, s) :
    if L>n-1 : 
        if s <= c :
            print(s)
        return       
    else :
        DFS(L+1, s+w[L])
        DFS(L+1,s)

if __name__=='__main__' :
    w=[]
    c, n = map(int, input().split())
    for i in range(n) :
        d=int(input())
        w.append(d)
    DFS(0,0)

==>s중에 가장 큰 값을 고르고 싶은데..저렇게 되면 c보다 작은 모든 s경우의 수 나옴

def DFS(L, s) :
    if L>n-1 : 
        global l
        if s<=c and l<s :
            l=s
        print(l)
        return
    else :
        DFS(L+1, s+w[L])
        DFS(L+1,s)
if __name__=='__main__' :
    w=[]
    c, n = map(int, input().split())
    for i in range(n) :
        d=int(input())
        w.append(d)
    DFS(0,0)

==> 이렇게 하면 가장 큰 값이 나오는데 비교될 때마다 출력돼가지고
짱 여러번 나온다 이 부분에서 막히네 ㅠㅠ
==========>그냥 여기서 l만 지정해놓고 return한 다음에
마지막줄, 저 DFS(0,0)인 데에다가 print(l) 하면 된다

최종 내 풀이

l=0
def DFS(L, s) :
    global l
    if L>n-1 :
        if s<=c and s>l:
            l=s
        return
    else :
        DFS(L+1, s+w[L])
        DFS(L+1,s)

if __name__=='__main__' :
    w=[]
    c, n = map(int, input().split())
    for i in range(n) :
        d=int(input())
        w.append(d)
    DFS(0,0)
    print(l)

====> 그런데 이거 시간초과 걸리고, 케이스5에서는 한참 걸린다
왜냐하면 일일이 비교해주니깐
======>더 가지치기를 해서 잘라주어야 한다

<풀이>

1차 풀이(이것은 시간 초과)


def DFS(L, sum):
    global result
    if sum>c:
        return
    if L==n:
        if sum>result:
            result=sum
    else:
        DFS(L+1, sum+a[L])
        DFS(L+1, sum)


if __name__=="__main__":
    c, n=map(int, input().split())
    a=[0]*n
    result=-2147000000
    for i in range(n):
        a[i]=int(input())
    DFS(0, 0)
    print(result)

2차 풀이 : 더 가지치기 하신 것
total(총 바둑이 무게의 합) - tsum(지금까지 경우의 수 만든 바둑이 무게의 합 = 앞으로 경우의 수 따져야할 남은 바둑이들 무게의 합
(이 위의 값 + sum) 했을 때 그 합이 result(지금까지 나왔던 합의 maximum)현재까지 구한 최적의 답 result보다 작다면 더 이상 다음 바둑이들 볼 필요가 없다


def DFS(L, sum, tsum):
    global result
    if sum+(total-tsum) < result : #지금까지 만든 부분집합 - 앞으로 판단해야 할 바둑이 무게의 합이 
        return                  #현재까지 구한 최적의 답 result보다 작다면 더 이상 다음 바둑이들 볼 필요가 없다
    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)