[백준] 연산자 끼워넣기 14888번 (python)

출처 : 14888번: 연산자 끼워넣기 (acmicpc.net)

14888번: 연산자 끼워넣기

풀이 방법

DFS로 완전 탐색으로 풀어야 한다.

연산자를 배열로 따로 넣어 두고 각 연산자가 남아 있으면 사용하고 연산자 배열에서 -1을 해주고

dfs를 호출하고 다시 연산자 배열에서 +1을 해주는 백트레킹 방식으로 풀이 하였다.

max_num = -987654321
min_num = 987654321
def dfs(index, sum):
    global min_num, max_num,path
    if index == N:
        min_num = min(min_num, sum)
        max_num = max(max_num, sum)
    for i in range(4):
        if (arithmetic[i] > 0):
            if (i == 0):
                arithmetic[i] -= 1
                dfs(index+1, sum+num[index])
                arithmetic[i] += 1
            elif(i == 1):
                arithmetic[i] -= 1
                dfs(index + 1, sum-num[index])
                arithmetic[i] += 1
            elif (i == 2):
                arithmetic[i] -= 1
                dfs(index + 1, sum * num[index])
                arithmetic[i] += 1
            elif (i == 3):
                arithmetic[i] -= 1
                dfs(index + 1,  int(sum / num[index]))
                arithmetic[i] += 1

N = int(input())
num = []
arithmetic = []
num = list(map(int, input().split()))
arithmetic = list(map(int, input().split()))

dfs(1, num[0])
print(max_num)
print(min_num)