[19번] 연산자 끼워 넣기

https://www.acmicpc.net/problem/14888

14888번: 연산자 끼워넣기

 

 

import itertools

N = int(input())
nums = list(map(int, input().split()))    
ops_cnt = list(map(int, input().split()))

ops = []
for cnt, op in zip(ops_cnt, ['+', '-', '*', '/']):
    for _ in range(cnt):
        ops.append(op)

candidates = itertools.permutations(ops)

max_v = -int(1e9)
min_v = int(1e9)
for ops in set(candidates):
    v = nums[0]
    for i in range(len(ops)):
        v = int(eval(str(v) + ops[i] + str(nums[i + 1])))
    max_v = max(max_v, v)
    min_v = min(min_v, v)

print(max_v)
print(min_v)

 

itertools 대신에 재귀로 푸는 방법 => 이 경우에는 이게 빠르다

 

def dfs(i, v):
    global add, sub, mul, div, max_v, min_v
    if i == N:
        max_v = max(max_v, v)
        min_v = min(min_v, v)
        return

    if add > 0:
        add -= 1
        dfs(i + 1, v + nums[i])
        add += 1
    if sub > 0:
        sub -= 1
        dfs(i + 1, v - nums[i])
        sub += 1
    if mul > 0:
        mul -= 1
        dfs(i + 1, v * nums[i])
        mul += 1
    if div > 0:
        div -= 1
        dfs(i + 1, int(v / nums[i]))
        div += 1


N = int(input())
nums = list(map(int, input().split()))
add, sub, mul, div = map(int, input().split())

max_v = -int(1e9)
min_v = int(1e9)
v = nums[0]
dfs(1, v)

print(max_v)
print(min_v)