[백준] 연산자 끼워넣기 (3)

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

15659번: 연산자 끼워넣기 (3)

연산자 우선순위를 다루는 문제입니다. 비슷한 문제를 풀어본 경험이 있어서 쉽게 풀이할 수 있었습니다. 숫자들의 순서는 정해져있으므로 연산자들의 순서를 정해준 다음 수식을 만들어주어 계산을 해주면 됩니다. 수식 계산의 포인트는 1. 후위 연산으로 바꾸기 2. 후위 연산식 계산하기 입니다.

 

후위 연산식으로 바꾸는 방법은 숫자를 만나면 바로 리스트에 넣어주고 연산자를 만나면 현재 연산자보다 낮은 연산자를 만날 때까지 스택에서 빼내어 리스트에 넣어주고 현재 연산자를 스택에 넣어줘야합니다. 

 

후위 연산식을 계산하는 방법은 숫자를 만나면 스택에 넣어주고 연산자를 만나면 스택에서 숫자 2개를 빼내어 계산을 해주고 다시 스택에 넣어주면 됩니다.

import sys
INT_MAX = sys.maxsize
sys.stdin = open("input.txt", "r")
input = sys.stdin.readline

n = int(input())

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

oper_cnt = list(map(int, input().split()))

PLUS = 101
MINUS = 102
MUL = 103
DIV = 104


operands = []


def calculate():
    prior = []
    stack = []

    # 후위 연산으로 바꾸는 방법
    for i in range(n):
        # 숫자 먼저 담기
        prior.append(nums[i])

        if i < n - 1:
            cur_oper = operands[i]

            # 더하기 빼기는 stack에 저장되어 있는 모든 연산자를 빼서 넣어준다.
            if cur_oper == PLUS or cur_oper == MINUS:
                while stack:
                    prior.append(stack.pop())
            else:
                while stack and (stack[-1] == MUL or stack[-1] == DIV):
                    prior.append(stack.pop())

            stack.append(cur_oper)
    # 남아있는 연사자들을 다 넣어준다.
    while stack:
        prior.append(stack.pop())

    for ex in prior:
        if ex > 100:
            num1 = stack.pop()
            num2 = stack.pop()

            if ex == PLUS:
                stack.append(num1 + num2)
            elif ex == MINUS:
                stack.append(num2 - num1)
            elif ex == MUL:
                stack.append(num2 * num1)
            else:
                stack.append(num2 // num1)
        # 숫자인 경우
        else:
            stack.append(ex)

    return stack[0]


min_ans = INT_MAX
max_ans = -INT_MAX

def perm(cnt):
    global min_ans, max_ans

    if cnt == n - 1:
        ret = calculate()

        min_ans = min(min_ans, ret)
        max_ans = max(max_ans, ret)

        return

    for i in range(4):
        if oper_cnt[i] > 0:
            oper_cnt[i] -= 1
            # 연산자 표시를 위해
            operands.append(i + 101)
            perm(cnt + 1)
            operands.pop()
            oper_cnt[i] += 1


perm(0)

print(max_ans)
print(min_ans)