[PY] 14888 : 연산자 끼워넣기

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

뭘 어떻게 하라는거야 생각했지만, 그냥 젠틀한 백트래킹이 필요했다. 백트래킹과 DFS 어딘가를 잘 이용하는 영역이라는데, 코드를 보면 이게 어떻게 DFS라고 칠 수 있지라는 생각이 든다. 백트래킹의 비중이 훨씬 높았던 문제.

import sys

numCnt = int(sys.stdin.readline())
numList = list(map(int, sys.stdin.readline().strip().split()))[:numCnt]

operator = list(map(int, sys.stdin.readline().strip().split()))[:4]
maxValue = float('-inf')
minValue = float('inf')

def truncate_division(a, b):
    result = a // b
    if a % b != 0 and ((a < 0) != (b < 0)):  # 음수 방향에서 조정
        result += 1
    return result

def dfs(totalValue, depth):
    global maxValue, minValue
    if(depth == (numCnt)):
        maxValue = max(totalValue, maxValue)
        minValue = min(totalValue, minValue)
    else:
        for i in range(4):
            if(operator[i] > 0):
                operator[i] -= 1
                if i == 0:
                    dfs(totalValue + numList[depth], depth + 1)
                elif i == 1:
                    dfs(totalValue - numList[depth], depth + 1)
                elif i == 2:
                    dfs(totalValue * numList[depth], depth + 1)          
                elif i == 3:
                    dfs(truncate_division(totalValue, numList[depth]), depth + 1)
                operator[i] += 1


dfs(numList[0], 1)
print(maxValue)
print(minValue)