백준 알고리즘 14888번 연산자 끼워넣기 풀이 with Python

문제 링크: https://www.acmicpc.net/problem/14888

14888번: 연산자 끼워넣기

문제는 아래와 같습니다.

14888번 연산자 끼워넣기

이 문제는 최솟값과 최댓값을 다 확인해야 하므로 완전탐색을 해야합니다. 저는 너비우선탐색(bfs)를 이용하여 문제를 해결하였습니다. 풀이는 다음과 같습니다.

from collections import deque
from copy import deepcopy


def solution(n, numbers, tools):
    maxi = -float('inf')
    mini = float('inf')
    queue = deque()
    # 더하기 빼기 곱하기 나누기
    queue.append([0, numbers[0], tools])
    while queue:
        count, sub, tool = queue.popleft()
        if count == n - 1:
            if maxi < sub:
                maxi = sub
            if mini > sub:
                mini = sub
        else:
            if tool[0] > 0:
                tool2 = deepcopy(tool)
                tool2[0] -= 1
                queue.append([count + 1, sub + numbers[count + 1], tool2])
            if tool[1] > 0:
                tool2 = deepcopy(tool)
                tool2[1] -= 1
                queue.append([count + 1, sub - numbers[count + 1], tool2])
            if tool[2] > 0:
                tool2 = deepcopy(tool)
                tool2[2] -= 1
                queue.append([count + 1, sub * numbers[count + 1], tool2])
            if tool[3] > 0:
                tool2 = deepcopy(tool)
                tool2[3] -= 1
                if (sub > 0 and numbers[count + 1] < 0) or (sub < 0 and numbers[count + 1] > 0):
                    sub2 = -(abs(sub) // abs(numbers[count + 1]))
                else:
                    sub2 = sub // numbers[count + 1]
                queue.append([count + 1, sub2, tool2])
    print(maxi)
    print(mini)


n = int(input())
number3 = list(map(int, input().split()))
tool3= list(map(int, input().split()))
solution(n, number3, tool3)