047 - 바둑이 승차(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 time
#import sys
#sys.stdin = open('in4.txt', 'rt')


def DFS(L):
    global res, c

    if L == n+1:
        sum = 0
        for i in range(1, n+1):
            if ch[i] == 1:
                sum += a[i-1]
        if sum > c:
            return
        else:
            if res < sum:
                res = sum
                # print('sum: {}, {}'.format(sum, ch))
    else:
        ch[L] = 1
        DFS(L+1)
        ch[L] = 0
        DFS(L+1)


def DFS2(L, sum):
    global res, c

    if sum > c:
        return
    elif L == n:
        if sum > res:
            res = sum
    else:
        DFS2(L+1, sum+a[L])
        DFS2(L+1, sum)


def DFS3(L, sum, tsum):
    global res, c

    # total-tsum 은 현재 레벨 하위의 모든 총합임.
    # 그래서 현재까지의 합 + 하위의 총합(모두 포함한다는 전제하에) < 현재 최대값,
    # 현재 최대값 보다 작으면 무조건 탈락하는 조건추가.
    if sum+(total-tsum) < res:
        return
    elif sum > c:
        return
    elif L == n:
        if sum > res:
            res = sum
    else:
        DFS3(L+1, sum+a[L], tsum+a[L])
        DFS3(L+1, sum, tsum+a[L])


if __name__ == '__main__':
    c, n = map(int, input().split())
    a = [int(input()) for _ in range(n)]
    ch = [0]*(n+1)
    total = sum(a)
    # print(c, n, a, total)
    
# 각 요소의 포함여부를 확인하고 합계를 구하는 방식
    res = 0
    start = time.time()
    DFS(1)
    end = time.time()
    print(f'DFS, {end-start:.6f}')
    print(res)

# 합계를 직접 구하는 방식
    res = 0
    start = time.time()
    DFS2(0, 0)
    end = time.time()
    print(f'DFS2, {end-start:.6f}')
    print(res)

# 합계를 직접 구하는 방식의 보완, 각 레벨기준으로 하위 무게를 모두 더 해도,
# 현재 최대값보다 작다면 의미가 없으므로 바로 return 해서 스킵하는 보완로직 추가
    res = 0
    start = time.time()
    DFS3(0, 0, 0)
    end = time.time()
    print(f'DFS3, {end-start:.6f}')
    print(res)

 

 

 

• 함수별 연산 속도를 시간으로 비교한 결과, 결과는 같지만 실행 시간이 차이나는 것을 볼 수 있다

 ~ python aa.py
22640
DFS, 4.257046
22640
DFS2, 0.569778
22640
DFS3, 0.000029

 

 

• 시간 비교용으로 사용한 데이터

100000000 21
27
567
999
234
50
567
123
4734
754
84
35
1353
76
464
4634
65
89
3553
59
38
4135