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

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

---

 

연산자가 어떻게 들어가느냐에 따라 값이 완전히 바뀌기 때문에 DFS를 활용하여 모든 결괏값을 비교하도록 하였다. 이때 중요한 것은 한 번 사용한 연산자는 -1을 해주어야 한다. 그리고 depth == n 일 때는 결과를 비교하고 나와야 한다.

 

그리고....

if else가 아니라 if 분기문으로 사용하기 때문에 반드시 메서드 인자에서 연산을 해야 한다. 처음에 연산값을 변수에 담은 후 dfs 메서드 인자로 넣었는데 그러면 답이 제대로 안 나온다. 확인해 보니 여러 분기문이 돌아가는 과정에서 계산값이 계속 바뀌어서 그렇다고 한다..

 

이렇게 작성하면 안 되고,

 

이렇게 작성해야 한다.

 

 

정답 코드

import sys
input = sys.stdin.readline

n = int(input())
numbers = list(map(int, input().split()))
operand = list(map(int, input().split()))

max_answer = -1e9
min_answer = 1e9

def dfs(depth, add, minus, multi, div, answer):
    global max_answer, min_answer
    if depth == n:
        max_answer = max(answer, max_answer)
        min_answer = min(answer, min_answer)
        return

    if add:
        dfs(depth+1, add-1, minus, multi, div, answer + numbers[depth])

    if minus:
        dfs(depth+1, add, minus-1, multi, div, answer - numbers[depth])

    if multi:
        dfs(depth+1, add, minus, multi-1, div, answer * numbers[depth])

    if div:
        if answer > 0:
            dfs(depth+1, add, minus, multi, div-1, answer // numbers[depth])
        else:
            dfs(depth+1, add, minus, multi, div-1, (-1)*(abs(answer) // numbers[depth]))

dfs(1, operand[0], operand[1], operand[2], operand[3], numbers[0])
print(max_answer)
print(min_answer)