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

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

풀이

1. N의 범위가 크지 않으므로, 재귀함수를 적용할 수 있다.

2.특정 재귀가 끝난 이후에는, 값을 특정 값으로 덮어 씌우면 오류가 발생하므로 직전 값으로 되돌릴 수 있는 로직을 구성하는 것이 중요하다.

3. 이 문제의 경우, 계산 이후 연산자 배열의 수를 -1한 이후 다시 +1을 하는 것으로 적용하며, 재귀함수의 매개변수로 현재 까지의 계산 값을 넘겨줌으로써 계산이 끝나 최대값과 최소값을 갱신한 이후 다시 이전 상태로 돌아올 수 있다.

제출 코드

import sys

n = int(input())
nums = list(map(int, input().split()))
sign = list(map(int, input().split()))

min_val = sys.maxsize
max_val = -sys.maxsize


def calculate(x, y, z):
    if z == 0:
        return x + y
    elif z == 1:
        return x - y
    elif z == 2:
        return x * y
    else:
        if x < 0:
            return -(-x // y)
        else:
            return x // y


def insert(cnt, now):
    global max_val, min_val
    if cnt == n - 1:
        min_val = min(min_val, now)
        max_val = max(max_val, now)
        return
    else:
        for i in range(4):
            if sign[i] > 0:
                sign[i] -= 1
                next_now = calculate(now, nums[cnt + 1], i)
                insert(cnt + 1, next_now)
                sign[i] += 1


insert(0, nums[0]) # 숫자들의 순서는 변하지 않으므로 첫 번째 값으로 시작
print(max_val)
print(min_val)