[백준/Python] 14888번 연산자 끼워넣기

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

14888번: 연산자 끼워넣기

---

---

Solution

def dfs(i, current):
    global arr, op, result
    
    #print(i, current)
    if i == n-1:
        result.append(current)
        return
    else:
        # +
        if op[0] > 0:
            op[0] -= 1
            dfs(i+1, current + arr[i+1])
            op[0] += 1
        # -
        if op[1] > 0:
            op[1] -= 1
            dfs(i+1, current - arr[i+1])
            op[1] += 1
        # x
        if op[2] > 0:
            op[2] -= 1
            dfs(i+1, current * arr[i+1])
            op[2] += 1
        # /
        if op[3] > 0:
            op[3] -= 1
            if current < 0:
                dfs(i+1, -1 * (abs(current) // arr[i+1]))
            else:
                dfs(i+1, current // arr[i+1])
            op[3] += 1

n = int(input())
arr = list(map(int, input().split(' ')))
op = list(map(int, input().split(' ')))

result = []

dfs(0, arr[0])
#print(result)
print(max(result))
print(min(result))

 

처음에는 연산자 네 개의 모든 경우의 수를 구해서 완전 탐색으로 푸는 방식으로 접근을 했는데 코드가 더 복잡해지기도 하고 dfs로 푸는게 더 간단하고 깔끔해서 dfs로 풀었다.

각 연산자의 경우에 대해서 다 쓸 때까지 재귀적으로 검사한다. 그리고 입력된 수의 개수만큼 재귀를 돌면 result에 담아 최대값과 최소값을 출력한다.