문제
N개의 수로 이루어진 수열이 주어집니다. 수와 수 사이에 끼워넣을 수 있는 N-1개의 연산자가 주어집니다. 연산자는 +, -, ÷, × 로 이루어져 있습니다.
수와 수사이에 연산자를 넣어 수식을 만들고 계산해서 결과가 최대인것과 최소인것을 구하는 문제입니다.
제약 조건
풀이
부등호문제(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])와 같음.