[백준 14888] 연산자 끼워넣기 - Python (백트래킹, DFS, 브루트포스)

 

14888번: 연산자 끼워넣기

 

 

<내 코드>

 

N = int(input())
nums = list(map(int, input().split()))
add, sub, mul, div = map(int, input().split())

# 비교값
max_ = -1e9
min_ = 1e9


def dfs(cnt, res, add, sub, mul, div):
    global max_, min_
    # 재귀 탈출 조건
    if cnt == N:
        max_ = max(res, max_)
        min_ = min(res, min_)
        return

    if add:
        dfs(cnt+1, res+nums[cnt], add-1, sub, mul, div)
    if sub:
        dfs(cnt+1, res-nums[cnt], add, sub-1, mul, div)
    if mul:
        dfs(cnt+1, res*nums[cnt], add, sub, mul-1, div)
    if div:
        dfs(cnt+1, int(res/nums[cnt]), add, sub, mul, div-1)


dfs(1, nums[0], add, sub, mul, div)
print(max_)
print(min_)

 

백트래킹을 이용해 모든 경우를 다 탐색하는 방법이다. 아직까지 재귀와 백트래킹 개념이 어려운 것 같다..