백준 | 연산자 끼워넣기

백준 연산자 끼워넣기

N개의 정수와 N - 1개의 연산자가 주어질 때, 아래의 조건을 만족하는 계산 결과의 최댓값과 최솟값을 구하는 문제이다.

[1] 연산자 우선 순위는 무시되며, 앞에서부터 순서대로 계산한다.
[2] 주어진 숫자의 순서는 바꾸면 안 된다.
[3] 나눗셈은 정수 나눗셈의 몫만 취한다.
[4] 음수를 양수로 나눌 때는 C++ 14의 기준을 따른다. 즉, 음수를 양수로 바꾼 뒤 몫을 취하고, 그 몫을 음수로 바꾼 것과 같다.

순열(itertools.permutations)을 활용했고, 중복 연산을 제거하기 위해 set()으로 형 변환했다.

import sys
from itertools import permutations

# 입력
n = int(sys.stdin.readline())
nums = list(map(int, sys.stdin.readline().split()))

operator_symbols = ['+', '-', '*', '/']
operator_count = list(map(int, sys.stdin.readline().split()))

operators = []
for i in range(4):
    operators.extend([operator_symbols[i]] * operator_count[i])

# 최댓값 및 최솟값 계산
max_result = float('-inf')
min_result = float('inf')

for ops in set(permutations(operators, n - 1)):
    result = nums[0]

    for i in range(n - 1):
        if ops[i] == '+':
            result += nums[i + 1]
        elif ops[i] == '-':
            result -= nums[i + 1]
        elif ops[i] == '*':
            result *= nums[i + 1]
        elif ops[i] == '/':
            if result < 0 and nums[i + 1] > 0:
                result = -(-result // nums[i + 1])
            else:
                result //= nums[i + 1]
    
    max_result = max(max_result, result)
    min_result = min(min_result, result)

# 출력
print(max_result)
print(min_result)