BOJ - 연산자끼워넣기2(15658)

실버2 : 완전 탐색 문제이다.

풀이

기존 것에 비해 연산자 개수가 늘어난 문제. 단순한 순열로 풀면 44P10의 연산 결과라 못푼다. 그냥 완전탐색으로 풀면되긴한데, 백준에서 pypy로 제출했더니 틀렸다고 해서 당황했다..

Code

import sys
 
input = sys.stdin.readline
 
n = int(input())
a = list(map(int, input().split()))
plus, minus, multi, div = map(int, input().split())
state = {"+": plus, "-": minus, "*": multi, "/": div}
maxNum, minNum = -1e11, 1e11
 
def go(idx, value):
    global maxNum, minNum
    if idx == n:
        maxNum = max(maxNum, value)
        minNum = min(minNum, value)
        return
 
    for op in "+-*/":
        if state[op]:
            state[op] -= 1
            go(idx + 1, int(eval(f"{value}{op}{a[idx]}")))
            state[op] += 1
 
go(1, a[0])
print(maxNum)
print(minNum)
 

Reference

• 백준(15658번) - 연산자 끼워넣기 2