바둑이 승차(DFS)

철수는 그의 바둑이들을 데리고 시장에 가려고 한다.

그런데 그의 트럭은 C킬로그램 넘게 태울 수가 없다.

철수는 C를 넘지 않으면서 그의 바둑이들을 가장 무겁게 태우고 싶다.

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

 

▣ 입력설명

첫 번째 줄에 자연수 C(1<=C<=100,000,000)와 N(1<=N<=30)이 주어집니다.

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

 

▣ 출력설명

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

 

▣ 입력예제

259 5

81

58

42

33

61

 

▣ 출력예제

242

---

내가 쓴 코드1

# 첫번째 코드
import sys
sys.stdin = open("input.txt", 'rt')

def DFS(idx, current_sum):
    global max
    if idx == N:
        if current_sum > max and current_sum < W:
            max = current_sum
    else:
        DFS(idx + 1, current_sum + lst[idx])
        DFS(idx + 1, current_sum)

if __name__ == '__main__':
    W, N = map(int, input().split())
    lst = []
    for _ in range(N):
        lst.append(int(input()))
    max = 0
    current_sum = 0
    DFS(0, current_sum)
    print(max)

 

내가 쓴 코드2

# 나의 두번째 코드
import sys
sys.stdin = open("input.txt", 'rt')

def DFS(idx, current_sum):
    global result
    if current_sum > W:
        return
    if idx == N:
        if current_sum > result:
            result = current_sum
    else:
        DFS(idx + 1, current_sum + weights[idx])
        DFS(idx + 1, current_sum)

if __name__ == '__main__':
    W, N = map(int, input().split())
    weights = []
    for _ in range(N):
        weights.append(int(input()))
    current_sum = 0
    result = 0
    DFS(0, current_sum)
    print(result)

 

내가 쓴 코드3

# 나의 세번째 코드
import sys
sys.stdin = open('input.txt', 'rt')

def DFS(idx, current_sum):
    global result
    if current_sum > W:
        return
    if idx == N:
        result = max(result, current_sum)
    else:
        if current_sum + weights[idx] <= W:
            DFS(idx + 1, current_sum + weights[idx])
        DFS(idx + 1, current_sum)

if __name__ == '__main__':
    W, N = map(int, input().split())
    weights = [int(input()) for _ in range(N)]
    current_sum = 0
    result = 0
    DFS(0, current_sum)
    print(result)

 

내가 쓴 코드4 -> 성공!!

#나의 네번째 코드 -> 성공!
import sys
sys.stdin = open("input.txt", 'rt')

def DFS(idx, current_sum):
    global result
    if current_sum > W:
        return
    if current_sum > result:
        result = current_sum
    if idx == N or current_sum + sum(weights[idx:]) < result:
        return
    DFS(idx + 1, current_sum + weights[idx])
    DFS(idx + 1, current_sum)

if __name__ == "__main__":
    W, N = map(int, input().split())
    weights = [int(input()) for _ in range(N)]
    current_sum = 0
    result = current_sum
    DFS(0, current_sum)
    print(result)

 

느낀점

1. 첫번재 코드로 풀었을 때 마지막 테스트케이스에서 시간초과가 떳당..
더 효율적으로 다시 구현해보장

2. 현재 무게의 합이 이미 주어진 리밋을 초과했으면 더 이상 재귀호출을 할 필요가
없으니 바로 return하는 방법을 통해(가지치기) 시간초과를 방지하고,
W보다 큰 최댓값이 나오는 것도 함께 방지할 수 있을 줄 알았으나!!
마찬가지로 똑같이 마지막 테스트케이스에서 시간초과..흑
다시 더 효율적으로 해보자.!

3. 가지치기를 좀 더 세밀하게 해봤다고 생각한 세번째 코드도 시간초과 ㅋ 다시!

4. 가지치기를 더 세밀하게 해봤다.
우선 현재 무게의 합이 주어진 리밋을 초과하면 더이상 재귀호출 안하고 리턴
최댓값 갱신 (리밋보다는 작을 것임)
더이상 탐색할게 없거나 뒤에 남은 무게를 전부 다 더해도 최댓값보다 작으면
더이상 재귀호출 안하고 리턴
성공!

5. DFS는 가지치기가 중요하구나! 모든 경우의 수를 전부 탐색하지않고
얼른얼른 리턴해버리는 가지치기 방법과 정도에 따라 시간효율성의 차이가 크다.

6. 뒤에 남은 무게를 전부 다 더해도 최댓값보다 작으면 리턴하는 가지치기가
시간 효율성에 가장 큰 영향을 미친 것 같다. 근데 그 구현방법이
난 내 코드가 더 맘에 드는데... 모범답안의 경우가 더 효율적인걸까!?
그런것같다. 매번 sum을 하는것보다 total에서 tsum을 빼는 단순 사칙연산이
훨씬 나을테니까..

7. 재귀함수를 정의할 때, 가지치기를 해버려야 하는 경우를 
if문으로 먼저 쓰고, 그 이후에 종료와 탐색 부분을 작성!

 

---

모범답안

# 모범답안
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)