[백준] 14888 연산자 끼워넣기 Python

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

14888번: 연산자 끼워넣기

재미있는 그래프 문제 !! 

사실 처음에는 itertools의 permutations 함수를 사용해서 연산자들의 조합을 n-1개 모두 고르는 순열 리스트를 

for문으로 돌리려고 했으나 시간초과가 떴다 ;;

dfs로 풀면 시간초과 없이 풀 수 있다.

상하좌우를 돌듯이 사칙연산을 재귀호출해주는 것이다 

i 는 인덱스이고 now는 현재 계산과정을 거치고 난 후의 값이다. 

i가 1로 시작하기 때문에 i == n 일 때 max, min 값을 비교하여 저장한다.

 

# 연산자 끼워넣기


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

def dfs(i , now):
    global min_result, max_result, add, sub, mul, div
    
    if i == n:
        max_result = max(now, max_result)
        min_result = min(now, min_result)
        
    if add > 0:
        add -= 1
        dfs(i+1, now+data[i])
        add += 1
    if sub > 0:
        sub -= 1
        dfs(i+1, now-data[i])
        sub += 1
    if mul > 0:
        mul -= 1
        dfs(i+1, now*data[i])
        mul += 1
    if div > 0:
        div -= 1
        dfs(i+1, int(now/data[i]))
        div += 1
    


dfs(1,data[0])


print(max_result)
print(min_result)