바둑이승차(DFS)

풀이1

• sum + 앞으로 판단할 바둑이 무게 합(total-tsum) < maxVal 일 때, 더 깊이 내려갈 필요 없음
• 다 더하는 경우에도 (앞으로 판단 할 바둑이를 다 데려가도) 현재 저장된 최댓갑 maxVal보다 작기때문

import sys
input=sys.stdin.readline

# 트럭허용무게, 바둑이 수
c,n=map(int, input().split())
# 바둑이 무게
arr=[0]*n
for i in range(n):
    arr[i]=int(input())

# 바둑이 총무게
total=sum(arr)

maxVal=0
def dfs(idx, sum, tsum):
    global maxVal
    # sum: 데려가는 바둑이 총 무게
    # tsum: 데려갈지 판단해본 바둑이 총 무게

    if sum+ (total-tsum) < maxVal:
        return
    if sum>c:
        return
    if idx==n:
        if maxVal<sum:
            maxVal=sum
    else:
        dfs(idx+1, sum, tsum+arr[idx]) # 더하지 않는 경우
        dfs(idx+1, sum+arr[idx], tsum+arr[idx])  # 더하는 경우

dfs(0,0, 0)
print(maxVal)

 

풀이2

import sys
input=sys.stdin.readline

# 트럭허용무게, 바둑이 수
c,n=map(int, input().split())
# 바둑이 무게
arr=[0]*n
for i in range(n):
    arr[i]=int(input())

maxVal=0
def dfs(idx, sum):
    global maxVal
    if sum>c:
        return
    if idx==n:
        if maxVal<sum:
            maxVal=sum
    else:
        dfs(idx+1, sum) # 더하지 않는 경우
        dfs(idx+1, sum+arr[idx])  # 더하는 경우


dfs(0,0)
print(maxVal)

 

풀이3

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

C(1<=C<=100,000,000)와 N(1<=N<=30)
259 5
81
58
42
33
61
"""
import sys
input=sys.stdin.readline

# 트럭허용무게, 바둑이 수
c,n=map(int, input().split())
# 바둑이 무게
arr=[]
for _ in range(n):
    arr.append(int(input()))

maxVal=0
def dfs(idx, sum):
    global maxVal

    if idx==n:
        return
    else:
        dfs(idx+1, sum) # 더하지 않는 경우
        dfs(idx+1, sum+arr[idx])  # 더하는 경우

        if sum+arr[idx]>c:
            maxVal=max(maxVal, sum)
        else:
            maxVal=max(maxVal, sum+arr[idx])

dfs(0,0)
print(maxVal)