백준 15658 연산자 끼워넣기(2)

16.45m

나의 답

import sys
input = sys.stdin.readline

n = int(input().rstrip())
nums = list(map(int, input().rstrip().split()))
ops = list(map(int, input().rstrip().split()))
MAX = -sys.maxsize
MIN = sys.maxsize

def bt(val, depth, add, minus, multi, div):
    global MAX, MIN
    if depth == n:
        MAX = max(val, MAX)
        MIN = min(val, MIN)
        return
    if add > 0: bt(val + nums[depth], depth + 1, add - 1, minus, multi, div)
    if minus > 0: bt(val - nums[depth], depth + 1, add, minus - 1, multi, div)
    if multi > 0: bt(val * nums[depth], depth + 1, add, minus, multi - 1, div)
    if div > 0: bt(int(val / nums[depth]), depth + 1, add, minus, multi, div - 1)

bt(nums[0], 1, ops[0], ops[1], ops[2], ops[3])
print(MAX)
print(MIN)

간단한 백트래킹 문제였다.
아니 근데 이문제 풀면서 dp라고 생각하고 풀었다...
오늘 재귀 DP 백트래킹 DFS의 차이점 글로 좀 정리해봐야겠다 ㄷ