백준 14888번: 연산자 끼워넣기 python

https://www.acmicpc.net/problem/14888

문제 접근

N개의 수와 N-1개의 연산자(+,-,x,/) 가 주어졌을 때 만들 수 있는 식의 결과가 최대, 최소 인 것을 구하라.
계산은 앞에서부터.

입력은 첫째 줄에 수의 개수 N,
둘째줄에 수열.
셋째줄에 연산자를 N-1개를 받는대 차례로 +,-,x,/ 의 개수로.

출력은
첫째 줄에 만들 수 있는 최댓값
둘째 줄에 만들 수 있는 최솟값

백트래킹으로 모든 처리를 다 들어가보며 max,min값을 구했다.

해답 및 풀이

import sys

input = sys.stdin.readline

n = int(input())
nums = list(map(int, input().split()))
add, sub, mul, div = map(int,input().split())

max_result = -1000000000
min_result = 1000000000

def dfs(index, current_result, add, sub, mul, div):
    global max_result,min_result # 파이썬에서 전역변수 가져다 쓰겠다는 의미

    # 모든 숫자를 다 사용했으면 결과 리턴
    if index == n:
        max_result = max(max_result, current_result)
        min_result = min(min_result, current_result)
        return
    
    # 각 연산자 별로 가능한 경우에 대해 탐색

    if add > 0:
        dfs(index+1, current_result + nums[index], add - 1, sub, mul, div)
    if sub > 0:
        dfs(index+1, current_result - nums[index], add, sub - 1, mul, div)
    if mul > 0:
        dfs(index+1, current_result * nums[index], add, sub, mul - 1, div)
    if div > 0:
        if current_result < 0:
            dfs(index+1, -(-current_result // nums[index]), add, sub, mul, div - 1)
        else:
            dfs(index+1, current_result // nums[index], add, sub, mul, div - 1)

dfs(1, nums[0], add, sub, mul, div)

print(max_result)
print(min_result)   

실행 흐름 :
add 분기로 들어가서 쭉 재귀 타고 내려감
끝까지 가면 index == n이 돼서 return
그럼 한 단계 위로 돌아와서 다음 if인 sub 시도
이걸 반복
마지막에는 div 분기까지 다 끝나면 → 그 함수도 return
모든 재귀 호출이 종료되면 프로그램도 종료