[BOJ] (DFS) 15658번 연산자 끼워넣기 (2)

 

permutation을 이용해 brute force로 처음에 접근을 했는데, 시간초과가 났다.

dfs로 풀면 시간초과를 피할 수 있다.

n = int(input())
arr = list(map(int, input().split()))
oper = list(map(int, input().split()))
maxval, minval = -1e9, 1e9

def solve(index, val, add, sub, mul, div):
    global maxval, minval
    if index == n:
        maxval = max(maxval, val)
        minval = min(minval, val)
        return 
    
    if add:
        solve(index+1, val+arr[index], add-1, sub, mul, div)
    if sub:
        solve(index+1, val-arr[index], add, sub-1, mul, div)
    if mul:
        solve(index+1, val*arr[index], add, sub, mul-1, div)
    if div:
        solve(index+1, int(val/arr[index]), add, sub, mul, div-1)
        
solve(1, arr[0], *oper)
print(maxval)
print(minval)

 

 

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

15658번: 연산자 끼워넣기 (2)