[DFS/BFS] 연산자 끼워넣기

"이것이 코딩테스트다(나동빈 저)"에서 나온 문제에 대한 코드를 다루고 있습니다.
문제에 대한 구체적인 설명과 조건 등은 책을 참고해주시기 바랍니다.

소요시간: 30분 + a

1. 문제 설명

- 숫자가 순서대로 N개 주어지고, 연산자가 N-1개 주어진다. 연산자를 수 사이에 넣어서 다양한 식을 만들 때, 그 결과가 최대가 되는 경우와 최소가 되는 경우를 출력하는 문제

2. 접근 방식

- DFS를 활용해서 문제를 푼다.

- +, -, *, / 연산자의 개수에 해당하는 만큼 연산을 수행할 수 있게 코드를 만든다. 

3. 코드

n = int(input())
data = list(map(int, input().split()))
add, minus, mul, div  = map(int, input().split())

min_value = 1e9
max_value = -1e9

def dfs(i, now):
    global data, add, minus, mul, div, n, min_value, max_value
    
    if i == n:
        min_value = min(min_value, now)
        max_value = max(max_value, now)
    else:
        if add > 0:
            add -= 1
            dfs(i+1, now + data[i])
            add += 1
        if minus > 0:
            minus -= 1
            dfs(i+1, now - data[i])
            minus += 1
        if mul > 0:
            mul -= 1
            dfs(i+1, now * data[i])
            mul += 1
        if div > 0:
            div -= 1
            dfs(i+1, int(now / data[i]))
            div += 1
            
dfs(1, data[0])
print(max_value)
print(min_value)

4. 코멘트

- 초기에는 Deque를 활용해서 BFS로 풀려고했으나, 메모리 초과로 문제를 풀지 못했다. 

- 연산자를 하나 빼서 DFS를 수행하고, 나올 때는 연산자를 다시 추가시킨다.   

- dfs를 넣을 때 i가 어떤 식으로 들어가는지를 주의깊게 볼 필요가 있다.