[파이썬 알고리즘 문제풀이 입문] 완전탐색 (백트랙킹, 상태트리와 CUT EDGE) / DFS(깊이우선탐색) 기초 - 바둑이 승차 (DFS)

*문제 본문은 강의 내용과 관련되어 있어 자세하게 적지 않았습니다.

 

 

 

문제

철수는 그의 바둑이들을 데리고 시장에 가려고 한다. 그런데 그의 트럭은 C킬로그램 넘게 태울 수가 없다. 철수는 C를 넘지 않으면서 그의 바둑이들을 가장 무겁게 태우고 싶다. N마리의 바둑이와 각 바둑이의 무게 W가 주어지면, 철수가 트럭에 태울 수 있는 가장 무거운 무게를 구하는 프로그램을 작성하세요.

 

 

 

 

풀이

• 답안 : Python

import sys
input = sys.stdin.readline

def DFS(index, sum, tsum):
    global result

    if sum+(total-tsum) < result:
        return

    if sum > C:
        return

    # C보다 작은 경우만 따짐
    if index == N:
        # 최대 무게 구하기
        if sum > result:
            result = sum
    else:
        DFS(index+1, sum+dogs[index], tsum+dogs[index])
        DFS(index+1, sum, tsum+dogs[index])
        
C, N = map(int, input().split())
dogs = [int(input()) for i in range(N)]

total = sum(dogs)
result = -1e9

DFS(0, 0, 0)
print(result)

- 이전 문제와 문제 풀이 방식은 거의 비슷하나, 시간 복잡도를 줄이기 위해 CUT EDGE를 추가로 해줘야 한다. (2번 진행)

 

   CUT EDGE 1 ) if sum+(total-tsum) < result

   → tsum : 부분집합으로 넣을지 안넣을지 이미 판단한 것들의 합

   → total - tsum : 앞으로 판단해야 할(아직 판단하지 않은) 바둑이들의 무게 합

   → 지금까지 구한 부분집합의 합(sum) + 앞으로 판단해야 할 바둑이들의 무게(total-tsum) 더했음에도 불구하고

      현재 최댓값으로 가지고 있는 result보다 작으면 return

 

   CUT EDGE2 ) if sum > C

   → 부분집합의 합(sum)이 C보다 큰 경우 return