[백준 14888]연산자 끼워넣기 Python

🎈최근 코테에서 좋지 않은 성적으로 인하여 코테 공부를 시작하였습니다!! 공부는 DFS, BFS, 시뮬레이션 + 구현 위주로 하도록 하겠습니다.

문제가 제시하는 바가 연산자를 숫자 사이에 끼워넣어 계산하였을 때 최댓값 최솟값을 구하는 문제이며, 연산 순서의 우선순위가 없기 때문에

"모든 경우의 수를 해보면 되겠구나!!"

라고 생각할 수 있었습니다. 그래서 DFS를 이용해서 모든 경우의 수를 계산하도록 코드를 작성하였습니다.

dfs 메소드에서는
1. 탐색의 깊이
2. 현재까지 연산 결과
3. 연산자 갯수
가 필요합니다. (연산자가 남지 않았으면 더이상 해당 연산자로는 계산이 불가능하기 때문!)

최종 depth에서 minNum, maxNum 과 비교하여 max값 또는 min값을 담도록 하면 됩니다.

결과물로 maxNum(최댓값), minNum(최솟값)을 출력합니다.

import sys
r = sys.stdin.readline

N = int(r().strip())
nums = list(map(int, r().split(" ")))
op = list(map(int, r().split(" ")))

minNum = 1e9
maxNum = -1e9

def dfs(depth, total, plus, minus, multiple, divide):
    global minNum, maxNum
    if depth == N:
        maxNum = max(maxNum, total)
        minNum = min(minNum, total)

    if plus:
        dfs(depth + 1, total + nums[depth], plus - 1, minus, multiple, divide)
    if minus:
        dfs(depth + 1, total - nums[depth], plus, minus - 1, multiple, divide)
    if multiple:
        dfs(depth + 1, total * nums[depth], plus, minus, multiple - 1, divide)
    if divide:
        dfs(depth + 1, int(total / nums[depth]), plus, minus, multiple, divide - 1)

dfs(1, nums[0], op[0], op[1], op[2], op[3])
print(maxNum)
print(minNum)