바둑이 승차

생성일: 2022년 2월 3일 오후 6:15

구현 코드

# 바둑이 승차 (DFS)
import sys
sys.stdin = open("input.txt", "rt")

def DFS(index, sum):
    global res
    if index == n:
        if sum < c and sum > res:
            res = sum
        else:
            return
    else:
        DFS(index+1, sum+l[index])
        DFS(index+1, sum)

if __name__ == "__main__":
    c, n = map(int, input().split())
    l = []
    for _ in range(n):
        l.append(int(input()))
    res = 0
    DFS(0, 0)
    print(res)

• 문제점 : n이 높아지면 실행 시간이 너무 길어져서 오답 처리가 된다.

모범답안

# 바둑이 승차 (DFS)
import sys
#sys.stdin = open("in5.txt", "rt")

def DFS(index, sum, tsum):
    global res
    if sum + (total-tsum) < res:
        return
    if sum > c:
        return
    if index == n:
        if sum > res:
            res = sum
        else:
            return
    else:
        DFS(index+1, sum+l[index], tsum+l[index])
        DFS(index+1, sum, tsum+l[index])

if __name__ == "__main__":
    c, n = map(int, input().split())
    l = []
    for _ in range(n):
        l.append(int(input()))
    res = 0
    total = sum(l)
    DFS(0, 0, 0)
    print(res)

차이점

• Cut Edge Tech (가지치기)

  • 내가 구현한 코드에서의 문제점인 실행시간을 대폭 줄일 수 있도록 조건문을 걸어서 정답의 조건에서 벗어난 경우 곧바로 함수를 return하도록 구성되어었다.

    if sum + (total-tsum) < res:
            return

  • 위의 코드가 추가 하여 트리 구조를 재귀를 통해 계속해서 검사를 하는 도중에 전체 리스트의 합(total)에서 현재까지 검사한 수들의 총합(tsum)을 뺀 값과 sum을 더했을 때(즉, 앞으로 트리에 속한 남은 값들을 전부 더한다고 가정했을 때) res 보다 작다면 끝까지 계산을 해서 더해도 정답(res)를 갱신할 수 없는 경우에 해당 되기 때문에 return으로 빠져 나오는 구조이다.