[Python] 연산자 끼워넣기 (백준 14888번 파이썬)

백준 14888번 연산자 끼워넣기

문제 바로가기

🙄 문제 이해

모든 연산자를 넣어보는 DFS(백트래킹) 문제입니다.
아이디어 자체는 잘 떠올렸는데, 최댓값/최솟값의 초기 설정에 오류가 있어 수정했더니 해결할 수 있었습니다.

📝 문제 풀이

일반적인 백트래킹 문제와 비슷하게 풀었습니다.

가지치기 하는 조건은 연산자의 갯수로, [사용한 연산자 수 -1] 를 통해 어떤 연산자의 갯수가 0이 되면 더이상 그 연산은 진행하지 않습니다.

최댓값과 최솟값의 초기값은 문제에서 주어진 수의 범위가 -10억~+10억 이므로 이와 같이 설정합니다.
초기에 범위를 확인하지 않고, 최댓값을 0으로 초기화했다가 이후 수정했습니다.

모든 연산자를 사용하고 마지막 수(idx==n)가 되면 더 사용할 연산자가 없으므로 종료합니다.
이때 최댓값과 최솟값을 리턴합니다.

💻 Python 코드

#백준 14888 연산자 끼워넣기

def maxmin(idx,plus,minus,mul,div,total):
    global max_res, min_res
    if idx == n:
        max_res = max(max_res, total)
        min_res = min(min_res, total)
        return

    if plus > 0:
        maxmin(idx+1,plus-1,minus,mul,div,total+num[idx])
    if minus > 0:
        maxmin(idx+1,plus,minus-1,mul,div,total-num[idx])
    if mul > 0:
        maxmin(idx+1,plus,minus,mul-1,div,total*num[idx])
    if div > 0:
        maxmin(idx+1,plus,minus,mul,div-1,int(total/num[idx]))

n = int(input())
num = list(map(int, input().split()))
plus,minus,mul,div = map(int, input().split())
idx = 1
total = num[0]
max_res = -1000000000
min_res = 1000000000

maxmin(idx,plus,minus,mul,div,total)

print(max_res)
print(min_res)