[ BOJ ] 14888 / 연산자 끼워넣기

문제

---

n개의 수로 이루어진 수열이 주어집니다.

수와 수 사이에 끼워 넣을 수 있는 n-1개의 연산자가 주어집니다.

연산자는 +, -, x, / 로만 구성됩니다.

주어진 수열의 순서를 바꾸는것은 안됩니다.

 

 

Solve

---

연산자의 순열을 구합니다.

operator = ['+', '+', '-', '*', '/']

arr = itertools.permutations(operator, len(operator))
print(len(list(arr))) # 120

('+', '+', '-', '*', '/') 이런게 겹치는 것을 확인할 수 있습니다.

이때 전체 길이는 120입니다.

 

 

arr = itertools.permutations(operator, len(operator))

arr_set = set(list(arr))
print(len(arr_set)) # 60

python의 set을 이용하여 중복을 제거해줍니다 (길이 60)

 

 

Code

---

import itertools
import sys

n = int(input())
num = list(map(int, input().split()))
arr = list(map(int, input().split()))

op = [ '+', '-', '*', '/' ]
operator = []

for i in range(len(arr)): # 0, 1, 2, 3
  for j in range(arr[i]): # 2, 1, 1, 1
    operator.append(op[i])


arr1 = itertools.permutations(operator, len(operator))
arr_set = set(list(arr1)) # 가능한 연산자 모음

max = -sys.maxsize
min = sys.maxsize

for ope in arr_set:

  result = num[0]

  for i in range(len(ope)): # i = 0, 1, 2, 3, 4
    if ope[i] == '+':
      result += num[i+1]
    elif ope[i] == '-':
      result -= num[i+1]
    elif ope[i] == '*':
      result *= num[i+1]
    else:
      if result < 0:
        result = (result*(-1)) // num[i+1]
        result *= (-1)
      else:
        result //= (num[i+1])

  if result >= max:
    max = result
  if result < min:
    min = result

print(max)
print(min)

 

dfs로 풀었을때에 비해 메모리와 시간이 많이 소요됐다