Baekjoon [14888] 연산자 끼워넣기 - python

 

14888번: 연산자 끼워넣기

 

문제 풀이

n = int(input())
number_list = list(map(int,input().split()))
operator_list = list(map(int,input().split())) #덧셈(+)의 개수, 뺄셈(-)의 개수, 곱셈(×)의 개수, 나눗셈(÷)의 개수이다.
min_num = 1e9
max_num = -1e9
def operator(depth, total,plus,minus,multi,div):
    global min_num
    global max_num
    # print(depth, max_num,min_num)
    if depth == n: # 백트래킹 끝나는 조건
        max_num = max(total, max_num)
        min_num = min(total, min_num)
        return
    if plus:
        operator(depth + 1,total + number_list[depth],plus-1,minus,multi,div)  # plus연산 수를 하나 뺴며, depth를 기반으로 숫자 idx탐색
    if minus:
        operator(depth + 1, total - number_list[depth], plus, minus - 1, multi, div) # minus연산 수를 하나 뺴며, depth를 기반으로 숫자 idx탐색
    if multi:
        operator(depth + 1, total * number_list[depth], plus, minus, multi - 1, div) # multi연산 수를 하나 뺴며, depth를 기반으로 숫자 idx탐색
    if div:
        operator(depth + 1, int(total / number_list[depth]), plus, minus, multi, div - 1) # div 연산 수를 하나 뺴며, depth를 기반으로 숫자 idx탐색


operator(1,number_list[0],operator_list[0],operator_list[1],operator_list[2],operator_list[3])
print(int(max_num))
print(int(min_num))
# print((-3//5))

 

문제 접근

min, max 변수를 통해 최대, 최소 값을 전달하며 depth를 통해 깊이 탐색을 진행합니다. DFS와 달리 주어진 조건에 맞춰 탐색을 하는것이아니라 전체적으로 다 탐색을 하면서 depth값이 n값이 되면 return을 하는 식으로 진행했습니다.

이때 if 문에서 elif문을 쓰지 않은 이유는 연산의 순서에 따라 최대, 최소 값이 바뀔 수 있기 때문에 

a @  b 연산에서 @에 넣을 수 있는 모든 연산자를 다 넣어보며 계산합니다.