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

🔗문제 링크 바로가기

이 문제는 가지치기 없이 모든 경로를 탐색해야하는 문제이다.
왜냐하면 중간 결과값이 크다고 해서 결과가 클 것이라는 보장도 없고, 중간이 작다고 해서 결과가 작다는 보장이 없기 때문이다. 즉, 어떤 연산자가 앞에 오든 최댓값이 될 수도 있고 최솟값이 될 수도있기 때문에 중도 포기가 불가능하다
그러나 가지치기가 없는데 왜 백트래킹 문제지? 라는 의문이 들었다.
그러나 백트래킹의 실제 정의는 더 넓다는 것을 알게되었다:

“상태를 변경하며 DFS로 탐색하고, 재귀가 끝나면 상태를 되돌리며 전 탐색 지점으로 복귀하는 알고리즘”

이 문제가 딱 그 문제이다.

import sys
input = sys.stdin.readline

N = int(input()) # 피연산자 개수
num = list(map(int, input().split())) # 피연산자
op = list(map(int, input().split())) # 연산자(+, -, *, //)

maximum = -1e9 # 가장 작은 값 대입
minimum = 1e9 # 가장 큰 값 대입

# depth: 사용한 숫자의 개수
# total: 누적 계산 값 
def dfs(depth, total, plus, minus, multiply, divide):
    global maximum, minimum # 전역변수 수정 권한
    
    if depth == N: # 모든 피연산자를 다 사용했을 때
        # maximum과 minimum은 재귀함수의 지역 변수가 아니기 때문에 재귀호출이 끝났더라도 값은 유지되므로 각 경우마다 max, min 갱신이 가능하다.
        maximum = max(total, maximum) 
        minimum = min(total, minimum) 
        return 
    
    
    if plus: # plus가 존재하면 첫번째 간격은 +로하고 이후 간격들 채우기
        dfs(depth + 1, total + num[depth], plus - 1, minus, multiply, divide) # 재귀호출 시작

    if minus: # minus가 존재하면 첫번째 간격은 -로 하고 이후 간격들 채우기
        dfs(depth + 1, total - num[depth], plus, minus - 1, multiply, divide)

    if multiply:
        dfs(depth + 1, total * num[depth], plus, minus, multiply - 1, divide)

    if divide:
        dfs(depth + 1, int(total / num[depth]), plus, minus, multiply, divide - 1)


dfs(1, num[0], op[0], op[1], op[2], op[3]) # depth = 1: 숫자 1개 사용
                                           # total = num[0]: 첫 번쨰 숫자 total에 대입하여 이후에 연산자로 갱신할거임
print(maximum)
print(minimum)
       

아래는 N = 3, num=[3,4,5], op=[1,0,1,0]인 경우에 코드 내부가 어떻게 돌아가는지 하나씩 해본 결과이다.