DFS 실전 적용 예시

• 결국 Backtracking에서 언젠간 벗어나야 한다.
• 시간복잡도 :
  Backtracking의 경우 80ms대
  DFS는 50ms대가 나온다.

-> 반드시 DFS로 갈아타자.

• 이 예시를 살펴보면 결국 DP와는 전혀 다른 개념임을 알 수 있다.
  비슷하게 재귀함수를 호출하는 건 맞지만, DP는 Memoization이나 Tabulation을 통해 시간을 줄여나가고, DFS는 한 가지 루트를 따라 계속해서 앞으로 나아가는 방식이다.

n = int(input())
numbers = list(map(int, input().split()))
plus, minus, product = map(int, input().split())
answer = []

def dfs(idx, plus, minus, product, ans):
    if idx == len(numbers) - 1:
        answer.append(ans)
        return
    if plus != 0:
        dfs(idx+1, plus - 1, minus, product, ans + numbers[idx+1])
    if minus != 0:
        dfs(idx+1, plus, minus - 1, product, ans - numbers[idx+1])
    if product != 0:
        dfs(idx+1, plus, minus, product - 1, ans * numbers[idx+1])


dfs(0, plus, minus, product, numbers[0])
print(min(answer), max(answer))