[백준] 14888번 연산자 끼워넣기 - 백트래킹(DFS)

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

14888번: 연산자 끼워넣기

 

DP로 풀 수 있지 않을까 했는데,

백트래킹을 이용하여 DFS로 짤 수 있어야 풀 수 있는 문제였다.

 

백트래킹은 

한정된 조건을 제시한 문제를 풀 때 쓰는 전략이다.

쉽게 설명해서 모든 경우의수를 시도하여 문제의 정답을 찾아나가지 않고(다중 for문)

시간을 단축하기 위해

한정된 조건에서 BFS나 DFS와 함께 구현한다.

 

 

백트랭킹의 특성

한정 조건에 부합하지 않는다면 이전 수행으로 돌아와야 하기 때문에 BFS보다는 DFS가 더 편하다.

 

백트래킹에 대한 더 자세한 설명은 아래 주소에서 보면 된다.

https://veggie-garden.tistory.com/24

[Python] 백트래킹 (+ DFS와 차이)

 

# BOJ_14888
# 23.3.5 일 5:38pm 시작 - 못품
# 입력
n = int(input())
nums = list(map(int, input().split()))
operators = list(map(int, input().split())) # + - * //
maximum, minimum = -1e9, 1e9


def dfs(depth, total, plus, minus, multiply, divide):
    global maximum, minimum
    if depth == n:
        maximum = max(total, maximum)
        minimum = min(total, minimum)
        return
    if plus:
        dfs(depth + 1, total + nums[depth], plus - 1, minus, multiply, divide)
    if minus:
        dfs(depth + 1, total - nums[depth], plus, minus - 1, multiply, divide)
    if multiply:
        dfs(depth + 1, total * nums[depth], plus, minus, multiply - 1, divide)
    if divide:
        dfs(depth + 1, total // nums[depth], plus, minus, multiply, divide - 1)

dfs(1, nums[0], operators[0], operators[1], operators[2], operators[3])
print(maximum)
print(minimum)

 

 

참고: https://velog.io/@kimdukbae/BOJ-14888-%EC%97%B0%EC%82%B0%EC%9E%90-%EB%81%BC%EC%9B%8C%EB%84%A3%EA%B8%B0-Python