연산자 끼워넣기

문제

N개의 수로 이루어진 수열이 주어집니다. 수와 수 사이에 끼워넣을 수 있는 N-1개의 연산자가 주어집니다. 연산자는 +, -, ÷, × 로 이루어져 있습니다.
수와 수사이에 연산자를 넣어 수식을 만들고 계산해서 결과가 최대인것과 최소인것을 구하는 문제입니다.

제약 조건

• 수열의 위치는 고정
• 연산자 우선순위 무시
• 나눗셈은 정수 나눗셈으로 몫만 취함(C++14기준)
• 연산자의 개수는 N-1, 수의 개수는 2<= N <= 11

풀이

부등호문제(https://velog.io/@6047198844/%EB%B6%80%EB%93%B1%ED%98%B8)와 상당히 유사한 문제입니다. 다만 고정되는 대상이 숫자이고, 순열로써 연산자의 모든 경우의 수를 고려하는것이 다릅니다.
수의 개수가 최대 11개일때 부등호의 개수는 11-1개 이므로 10!의 경우의 수를 모두 따져볼 수 있습니다.

부등호의 개수에 따라서 부등호 집합을 생성합니다. 해당 부등호 집합에 대한 순열을 모두 구하고 set()처리로 중복을 없앱니다. set()처리가 된 부등호 집합에 대해 부등호문제처럼 연산을 진행하면 됩니다.

set()처리를 해주는 이유는 다음과 같습니다.
"++-" 의 경우 "++-", "+-+", "++-", "+-+", "-++", "-++"의 순열 집합을 가집니다. 중복된 원소로 순열을 진행했기 때문에 중복된 순열원소가 존재하는것을 확인 가능합니다.

코드

'''
Created by jun on 21/05/18
'''
import sys
from itertools import permutations

N = int(input())
A = list(map(int, input().split()))
opers = ''.join(['+', '-', '*', '/'][idx] * i
               for idx, i in enumerate(map(int, input().split())))

min_res = sys.maxsize
max_res = -sys.maxsize

#set중요.
for oper in set(permutations(opers, N-1)):
    res = A[0]
    for i in range(0, N-1):
        if oper[i] == '+':
            res += A[i+1]
        elif oper[i] == '-':
            res -= A[i+1]
        elif oper[i] == '*':
            res *= A[i+1]
        else:
            if res < 0:
                res = -(-res // A[i+1]) #int(res/A[i+1])와 같다.
            else:
                res //= A[i+1]
    min_res = min(res, min_res)
    max_res = max(res, max_res)

print(max_res)
print(min_res)

새로 알게된 사실

중복된 원소로 순열을 만들때 중복 순열이 발생함.
res = -(-res // A[i+1])은 int(res/A[i+1])와 같음.