[Python] 백준 / silver / 14888번 (연산자 끼워넣기)

문제 링크 : https://www.acmicpc.net/problem/14888

백트래킹 연습중이다. N-Queen 문제에서 느꼈던 것처럼 백트래킹 문제를 풀때는 state space tree를 그려보면 헷갈리지 않다.

음수를 양수로 나눌 때는 C++14의 기준을 따른다는 것만 주의해주면 어렵지 않은 백트래킹 문제였다.

정답 코드

import sys
N = int(sys.stdin.readline())
num = list(map(int, sys.stdin.readline().split()))
oper = [0, 0, 0, 0]    # + - * /
oper[0], oper[1], oper[2], oper[3] = map(int, sys.stdin.readline().split())

minV = 10**9
maxV = -10**9


def dfs(x, result, op):
    global minV, maxV

    if x == N-1:
        minV = min(minV, result)
        maxV = max(maxV, result)
        return

    for i in range(4):
        if op[i] >= 1:
            op[i] -= 1
            if i == 0:
                dfs(x+1, result + num[x + 1], op)
            elif i == 1:
                dfs(x+1, result - num[x + 1], op)
            elif i == 2:
                dfs(x+1, result * num[x + 1], op)
            elif i == 3:
                if result < 0:
                    dfs(x+1, -(-result // num[x+1]), op)
                else:
                    dfs(x+1, result // num[x + 1], op)
            op[i] += 1


dfs(0, num[0], oper)

print(maxV)
print(minV)