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

정답 코드

# 백트래킹으로 풀어보기

N = int(input())
M = list(map(int, input().split()))
# 순서대로 +,-,*,//
add, sub, mul, div = map(int, input().split())

def dfs(n, sm, add, sub, mul, div):\


    global mn, mx
    # 종료 조건(정답처리)
    if n == N:
        mn = min(mn, sm)
        mx = max(mx, sm)
        return
    
    # 연산자 개수 남았을 경우에만 호출
    if add > 0:
        dfs(n+1, sm+M[n], add-1, sub, mul, div)
    if sub > 0:
        dfs(n+1, sm-M[n], add, sub-1, mul, div)
    if mul > 0:
        dfs(n+1, sm*M[n], add, sub, mul-1, div)
    if div > 0:
        dfs(n+1, int(sm/M[n]), add, sub, mul, div-1)


mx = int(-1e9)
mn = int(1e9)

dfs(1, M[0], add, sub, mul, div)
print(mx, mn)

• 계산 결과값 범위가 문제에 주어져있어서 설정해준다
• 연산자 개수를 따로 따로 받아서 계산할 연산자가 남았을 경우 계산해주고 다시 dfs 탐색해준다

도저히 모르겠어서
https://www.youtube.com/watch?v=6mbVfrwb3Qc
강의를 참고했다

백트래킹 가지치기
-> 현재 상태에서 다음 상태로 가는 모든 경우의 수를 찾아서 이 모든 경우의 수가 더이상 유망하지 않다고 판단되면 이전의 상태로 돌아감
-> 더이상 탐색할 필요가 없는 상태를 제외하는 것이 가지치기