14888번 연산자 끼워넣기

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

---

아이디어

코드를 보면 알겠는데 아직 백트래킹 아이디어 떠올리기가 쉽지 않다.
내가 막혔던 부분은 1) 연산자를 이미 사용했다면 빼야하는데 이걸 빼면 리스트에도 반영이 되니까 어떤 식으로 빼야할지 2) +가 있는지 -가 있는지 어떻게 확인을 하느냐였다. 그래서 처음에 반복문으로 하다가 무한 재귀에 빠졌었다.

그래서 해결한 방법은 더하기, 빼기, 곱하기, 나누기의 개수를 인수로 넣고 사용했다면 -1을 해주면 된다. 이렇게 하게 되면 원래 값에는 영향이 안간다.(백트래킹이므로) 이 아이디어만 떠올렸다면 금방 풀었을 것 같다.

---

코드

import sys
input = sys.stdin.readline

def dfs(idx, result, plus, minus, multiply, divide):
    global min_value, max_value

    if idx == n:
        max_value = max(max_value, result)
        min_value = min(min_value, result)
        return

    if plus:
        dfs(idx+1, result+num[idx], plus-1, minus, multiply, divide)
    if minus:
        dfs(idx+1, result-num[idx], plus, minus-1, multiply, divide)
    if multiply:
        dfs(idx+1, result*num[idx], plus, minus, multiply-1, divide)
    if divide:
        dfs(idx+1, int(result/num[idx]), plus, minus, multiply, divide-1)


n = int(input())
num = list(map(int, input().split()))
oper = list(map(int, input().split()))
min_value = float('inf')
max_value = float('-inf')

dfs(1, num[0], oper[0], oper[1], oper[2], oper[3])
print(max_value)
print(min_value)