[백준 - Python] 14888. 연산자 끼워넣기 (완전 탐색)

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

14888번: 연산자 끼워넣기

 

코드

N = int(input())
num = list(map(int, input().split()))
op = list(map(int, input().split()))  #   +,  -,  *,  / 의 개수가 순서대로 들어옴

maximum = -1e9
minimum = 1e9

def backtrack(depth, total, plus, minus, multiply, divide):
    global maximum, minimum
    if depth == N:
        maximum = max(total, maximum)
        minimum = min(total, minimum)
        return

    # 연산이 남아 있는지 확인 > 남은 연산 처리된 인자 값으로 재귀
    if plus:
        backtrack(depth + 1, total + num[depth], plus - 1, minus, multiply, divide)
    if minus:
        backtrack(depth + 1, total - num[depth], plus, minus - 1, multiply, divide)
    if multiply:
        backtrack(depth + 1, total * num[depth], plus, minus, multiply - 1, divide)
    if divide:
        backtrack(depth + 1, int(total / num[depth]), plus, minus, multiply, divide - 1)


backtrack(1, num[0], op[0], op[1], op[2], op[3])
print(maximum)
print(minimum)

 

다른 분들의 풀이를 참고했다.

 

연산자의 개수만큼 탐색을 하고,

연산자가 존재하면 그 연산을 수행하며 재귀 호출로 탐색을 진행하다.

 

재귀가 여러 가지로 뻗어나가기 때문에

최대 최소 값을 담아주는 변수는 전역 처리를 하였다.

 

백트래킹의 변형 풀이로 볼 수 있는데,

해결책에 대한 후보군을 구성하고

그 후보군이 문제의 조건을 만족하는지 여부를 검사해가며 해답을 찾는 방식이다.

 

문제에서 연산자 우선순위와 관계 없이

앞에서 부터 계산이 된다고 했으므로

backtrack 함수의 total 값에 각 연산을 수행한 후의 값을 인자로 넣어주면 된다.