바둑이 승차

문제 포인트

• 트럭에 바둑이를 태우는데, 트럭은 C 킬로그램 넘게 태울 수 없다.
• C를 넘지 않으면서 바둑이를 가장 무겁게 태우고 싶다.
• 트럭에 태울 수 있는 가장 무거운 무게를 출력하라
• N: 바둑이 마릿수, W: 각 바둑이의 무게

생각 포인트

• 경우의 수를 따지며, 문제에서 요구하는 최적의 해를 구해야하는 문제
• 따라서 DFS를 사용하여 풀겠다.

my_solution

def recursive(level, sum):
    global largest

    if sum > c:
        return

    if level == n:
        if sum > largest:
            largest = sum

    else:
        recursive(level + 1, sum + weights[level])
        recursive(level + 1, sum)


print(largest)

my_solution 해석

• 재귀를 사용한다.
• 입력값이 굉장히 많고 큰 경우에 타임 아웃
  • 불필요한 연산을 하지 않는 케이스를 생각하여 불필요한 연산을 진행하지 않도록 하는 cut-edge 부족
  • 이번 문제에서는 다음과 같은 과정이 필요했다.
    • 현재까지 태우기로 한 바둑이 무게의 합(sum)
    • 주어진 바둑이 전체 무게의 합(total)
    • 트럭에 태우기로 판단한 바둑이의 무게(total_sum)
    • total - total_sum: 앞으로 태워야 할 바둑이의 무게
    • total - total_sum + sum < result: 현재까지 태우기로 판단한 무게와 앞으로 태울 무게를 더했는데도 현재 구한 최적의 해보다 작다면 이는 더이상 최적의 해일 수 없기 때문에 추가 연산을 하지 않는다.

solution

result = -2147000000
total = sum(weights)


def recursive(level, sum, total_sum):
    global result

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

    if level == n:
        if sum > result:
            result = sum
    else:
        recursive(level + 1, sum + weights[level], total_sum + weights[level])
        recursive(level + 1, sum, total_sum + weights[level])


recursive(0, 0, 0)