Algorithm - 바둑이 승차(DFS)

 

알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다.
개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다.

 

문제

[바둑이 승차(DFS)]

 

철수는 바둑이들을 데리고 시장에 가려고 한다. 그런데 그의 트럭은 C킬로그램을 넘게 태울 수가 없다. 철수는 C킬로그램을 넘지 않으면서도 그의 바둑이들을 가장 무겁게 태우고 싶어한다.

 

N마리의 바둑이와 각 바둑이의 무게 W가 주어지면, 철수가 트럭에 태울 수 있는 가장 무거운 무게를 구하는 프로그램을 작성하시오.

 

 

*입력 설명

첫 번째 줄에 자연수 C(1 ≤ C ≤ 100,000,000)와 N(1 ≤ N ≤ 30)이 주어진다.

두 번째 줄부터 N마리의 바둑이의 무게가 주어진다.

 

*출력 설명

첫 번째 줄에 가장 무거운 무게를 출력한다.

 

 

---

 

 

풀이(Python)

답안

import sys
sys.stdin = open('AA/input_47.txt', 'rt')

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)
    
# 출력 : 242

 

input_47.txt(입력)

259 5
81
58
42
33
61

 

 

중요내용

1. 5마리 바둑이들의 무게를 각 원소로 하는 집합을 전체 집합으로 생각하고, 트럭에 태울 수 있는 바둑이들의 무게를 원소로 하는 집합을 부분집합으로 생각하여 문제 풀이에 접근한다.
2. 리스트 a는 각각의 바둑이들 무게를 저장하기 위해 선언한 리스트이다.
3. DFS() 함수의 인자 L은 리스트 a의 인덱스 번호를 의미한다. (각 바둑이들의 무게에 접근하는 인덱스 번호)
4. DFS() 함수의 인자 sum은 트럭에 태울 수 있는 바둑이들의 무게 합을 의미하는 부분집합이다.
5. 참고로, DFS() 함수 내에서 변수 result를 선언하고 있기 때문에(ex. result = sum), global result의 코드를 써줘야만 해당 변수를 전역 변수로 인식하여 에러가 발생하지 않는다. (해당 함수내에 지역 변수 result가 없기 때문)
6. 변수 total은 전체 바둑이의 무게 총합을 의미하는 변수이다.
7. 변수 tsum은 지금까지 승차 여부를 고려한 바둑이들의 무게 총합을 의미하는 변수이다.
8. total - tsum은 아직 승차 여부를 고려하지 않은 바둑이들의 무게 총합을 의미한다.
9. sum + (total - tsum)은 지금까지 승차한 바둑이의 무게와 아직 고려하지 않은 바둑이들의 무게 총합을 더한 값이다.
10. 만약, sum + (total - tsum) 값이 지금까지 구한 sum의 최대 값(result) 보다 작다면 더 이상 남은 바둑이들의 승차를 고려할 필요가 없으므로 함수의 동작을 정지시키는 return을 사용한 것이다. (시간 복잡도를 개선하기 위함)