[BOJ] 연산자 끼워넣기

---

코드

import sys
from itertools import permutations
input = sys.stdin.readline

# 입력
N = int(input())
A = list(map(int, input().split()))
a, b, c, d = map(int, input().split())
opl = []    # 연산자리스트
opl += ['+']*a
opl += ['-']*b
opl += ['*']*c
opl += ['//']*d

# 연산자 경우의수
perm = permutations(opl, len(opl))
perm = list(set(perm))    # 중복제거
ans_min = 10e9
ans_max = -10e9

for i in range(len(perm)):
    ans = A[0]
    for j in range(N-1):
        op = perm[i][j]
        next = A[j+1]
        if op == '+':
            ans += next
        elif op == '-':
            ans -= next
        elif op == '*':
            ans *= next
        else:
            if ans < 0:
                ans = -(-ans // next)
            else:
                ans //= next
    if ans <= ans_min:
        ans_min = ans
    if ans >= ans_max:
        ans_max = ans

print(ans_max)
print(ans_min)
            

결과

풀이 방법

• 수의 개수가 최대 11개이므로 4가지 연산자의 개수도 최대 10개이다. 그래서 연산자 순열을 구하여 일일이 브루트포스 방식으로 계산해도 괜찮을 것이라 생각하였다.
• 따라서 10개의 연산자들 순열을 itertools.permutations 라이브러리를 사용하여 구한 다음 중복된 것을 제거하였다.
• 그리고 각 연산자 순열에 대해 피연산자(A) 계산을 진행하며 하나의 연산자 순열을 사용한 계산이 끝날 때마다 최소값 또는 최대값을 갱신하였다.

---