백준 14888 (python): 연산자 끼워넣기

import itertools

maxNum = float('-inf')
minNum = float('inf')

def cal(numList, operList, result):
    global maxNum, minNum
    
    if not numList:
        if maxNum < result:
            maxNum = result
        if minNum > result:
            minNum = result
        return
    
    newNumList = numList[:]
    oper = operList.pop(0)
    
    if oper == "+":
        result = result + newNumList.pop(0)
    elif oper == "-":
        result = result - newNumList.pop(0)
    elif oper == "*":
        result = result * newNumList.pop(0)
    else:
        result = int(result/newNumList.pop(0))
    
    cal(newNumList, operList, result)

N = int(input())
numList = list(map(int, input().split()))
operList = []
operInput = list(map(int, input().split()))
basicOper = ["+", "-", "*", "/"]

# 연산자 배열 생성
for i in range(4):
    for j in range(operInput.pop(0)):
        operList.append(basicOper[i])
operIterList = list(set(itertools.permutations(operList, N-1)))

num = numList.pop(0)
for i in operIterList:
    cal(numList, list(i), num)

print(maxNum)
print(minNum)

 

이틀 걸려서 풀었다

`int(result/newNumList.pop(0))` 하면 음수/양수가 연산된다

 

처음에 제출한 코드에는 순열의 중복을 제거해주지 않아서 시간초과가 떴다. (PyPy로는 정답!)

그래서 `liset(set())`을 사용하여 중복을 제거해주니 통과가 됐다

 

다른 방법도 찾아봐야지

그리고 재귀로 풀지 않고 for문 써도 되는 듯 .. ㅠ 어렵다 증말

 

n = int(input())
number = list(map(int, input().split()))
add, sub, mul, div = map(int, input().split());
max_result = - int(1e9)
min_result = int(1e9)

def dfs(add, sub, mul, div, sum, idx):
    global max_result, min_result
    if idx == n:
        max_result = max(max_result, sum)
        min_result = min(min_result, sum)
        return
    if add:
        dfs(add-1, sub, mul, div, sum + number[idx], idx + 1)
    if sub:
        dfs(add, sub-1, mul, div, sum - number[idx], idx + 1)
    if mul:
        dfs(add, sub, mul-1, div, sum * number[idx], idx + 1)
    if div:
        dfs(add, sub, mul, div-1, int(sum / number[idx]), idx + 1)
        
dfs(add, sub, mul, div, number[0], 1)
print(max_result)
print(min_result)

 

 

이런 방법도 있구나 신기하다

if add, sub, mul, div로 연산자 랜덤 순서를 지정해주는 듯