재귀함수 이용한 문제 풀어보기 - 바둑이 승차

❓ 문제

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

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

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

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

 

📍 예제

// 입력예제
259 5
81
58
42
33
61

// 출력예제
242

 

 

💡 해결하기

➡️ 기본 원리는 부분집합 구하기에서 사용했던 방식을 사용하면 된다.

재귀 함수로 부분집합 구해보기 (tistory.com)

재귀 함수로 부분집합 구해보기

 

➡️ C 킬로그램이 넘게 바둑이를 태울 수 없다고 하였으므로 현재까지 승차한 바둑이의 무게 합(_sum)이 C보다 크면 현재 진행중인 함수를 종료해야 한다.

 

➡️ 바둑이 승차를 진행하면서 최대로 태울 수 있는 무게를 기록할 변수 하나(answer)를 만든다. 바둑이 무게를 하나씩 순서대로 돌면서(w 리스트를 순서대로 돈다. 인덱스는 i!) 승차 조합을 완성하였을 때, 선택된 바둑이들의 무게 합(_sum)이 지금까지의 가능한 최대 무게 (answer)보다 더 크다면 answer의 값을 현재 _sum으로 업데이트 한다.

 

➡️ 종료 조건에 해당하지 않는 경우 DFS 함수를 재귀 호출하여 진행한다.

현재 i번째의 바둑이를 승차하는 경우(_sum + w[i])와 승차시키지 않는 경우(그냥 _sum 그대로 가지고 가기) 2가지를 구현해야 한다.

 

➡️ 여기까지만 하면 큰 입력이 들어갔을 때 시간이 초과될 수 있으므로 코드를 더 최적화해야 한다.

최적화는 현재까지 거친 바둑이들 바로 뒤 순서에 있는 모든 바둑이들의 무게 합을 나타내는 total - total_sum 을 통해 이룰 수 있다. (total은 모든 바둑이들의 무게 합, total_sum은 현재까지의 모든 바둑이 무게 합)

앞으로 승차할 가능성이 있는 모든 바둑이들의 무게 합(total - total_sum)을 현재까지 승차한 바둑이의 무게 합에 더해 이것이 answer보다 더 작은 값이면 답이 될 가능성이 0이기 때문에 여기서 끊는 식(현재 함수 종료)으로 코드를 최적화한다.

(재귀 호출 시마다 그때의 i번째 바둑이의 무게를 total_sum에 계속 누적해야 한다.)

 

➡️ DFS 함수가 완전히 종료되면 answer에 저장되어 있는 값을 출력하면 된다.

 

 

 

💻 Python으로 코드 작성하기

 

# i : w 리스트에 접근하기 위한 index
# _sum : 현재까지 승차한 바둑이들의 무게 합
# total_sum : 현재까지 거친 바둑이들의 무게 합 (승차 여부 상관 X)
def DFS(i, _sum, total_sum):    
    global answer
    # 앞으로 포함될 가능성이 있는 바둑이들의 무게들을 모두 현재 _sum에 더했을 때 현재까지의 최대 무게보다 적으면 더 살펴볼 필요 X
    if _sum + (total - total_sum) < answer:     
        return
    # 현재 승차한 바둑이들의 무게가 제한을 넘을 경우
    elif _sum > c:     
        return
    # 마지막 무게까지 다 돌았을 경우 (트리에서 말단 노드에 도착하였을 때)
    elif i == n:     
        # 바둑이 무게의 합이 현재 탑승 가능 최대 무게보다 더 클 경우
        if _sum > answer:
            answer = _sum
    else:
        # 현재 순서의 바둑이를 승차시킬 경우
        DFS(i + 1, _sum + w[i], total_sum + w[i])
        # 현재 순서의 바둑이를 승차시키지 않을 경우
        DFS(i + 1, _sum, total_sum + w[i])
        

c, n = map(int, input().split())     # c : 트럭에 태울 수 있는 최대 무게, n : 철수가 데리고 있는 바둑이들의 수
w = [int(input()) for _ in range(n)]     # 바둑이들의 무게
answer = 0     # 철수가 트럭에 태울 수 있는 가장 무거운 무게
total = sum(w)     # 모든 바둑이들의 무게
DFS(0, 0, 0)
print(answer)

 

 

 

📌 참고 강의

파이썬 알고리즘 문제풀이 입문(코딩테스트 대비) 대시보드 - 인프런 | 강의 (inflearn.com)

파이썬 알고리즘 문제풀이 입문(코딩테스트 대비) - 인프런 | 강의