[TIL] 백준 - 연산자 끼워넣기

[Today I Learned]

# 백준 - 연산자 끼워넣기

문제
N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 N-1개의 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다.
우리는 수와 수 사이에 연산자를 하나씩 넣어서, 수식을 하나 만들 수 있다. 이때, 주어진 수의 순서를 바꾸면 안 된다.
N개의 수와 N-1개의 연산자가 주어졌을 때, 만들 수 있는 식의 결과가 최대인 것과 최소인 것을 구하는 프로그램을 작성하시오.

 

@solution.py

DFS 방향성은 금방 캐치 했는데, 전달하는 인수를 컨트롤하는데 애를 먹었다. 비슷한 문제를 풀 때 항상 겪는 문제 : /
다른 사람들 코드를 참고해 코드를 완성했다.

n = int(input())
numbers = list(map(int, input().split())) 
operators = list(map(int, input().split())) # +, -, x, //

minimum = 1e+09
maximum = -1e+09

def dfs(depth, cur, ops):
    global minimum, maximum

    if depth == n:
        if cur > maximum:
            maximum = cur

        if cur < minimum:
            minimum = cur
        
        return

    if ops[0] > 0:
        ops[0] -= 1
        dfs(depth+1, cur + numbers[depth], ops)
        ops[0] += 1

    if ops[1] > 0:
        ops[1] -= 1
        dfs(depth+1, cur - numbers[depth], ops)
        ops[1] += 1

    if ops[2] > 0:
        ops[2] -= 1
        dfs(depth+1, cur * numbers[depth], ops)
        ops[2] += 1

    if ops[3] > 0:
        ops[3] -= 1
        dfs(depth+1, int(cur / numbers[depth]), ops)
        ops[3] += 1
   
dfs(1, numbers[0], operators)

print(maximum)
print(minimum)

우선 minimum과 maximum을 매번 전달하지 않기 위해서 global 변수로 선언했다. 또 depth 변수를 두어 재귀 종료 조건을 표현했고, 이번 턴에 계산할 숫자를 불러올 때에도 사용했다. (numbers[depth]) 

다만 남은 연산 개수를 뺐다가 다시 더하는 점이 마음에 안들었는데, 아예 plus, minus ... 이렇게 연산자 별로 개수를 각기 다른 변수로 관리하는 방법을 사용해도 괜찮을 것 같다.