BOJ - 연산자 끼워넣기 14888번 (python)

❓ 문제 - 백준 연산자 끼워넣기 14888번 - python 풀이법

출처 

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

14888번: 연산자 끼워넣기

 

 

 

📝 문제해결법

1. 이 문제는 백트래킹(dfs)으로 풀었다.

• (+, -, *, /)의 연산자의 수를 add, sub, mul, div로 입력받는다.
• dfs()함수를 통해, 모든 숫자의 연산이 완료(depth=n) 되었으면 max_value와 min_value의 값을 갱신해준다.
• add, sub, mul, div 연산자의 갯수가 남았을 때까지 재귀함수를 통해 dfs를 돌린다.
• 특히 div, int(num/data[depth])를 통해 나눗셈 처리를 잘 해준다.

 

 

 

💻 소스코드

n = int(input())
data = list(map(int, input().split()))
add, sub, mul, div = map(int, input().split())
visited = [False for _ in range(n-1)]
max_value = -int(1e9)
min_value = int(1e9)

def dfs(depth, num, add, sub, mul, div):
    global max_value, min_value
    if depth == n:
        max_value = max(max_value, num)
        min_value = min(min_value, num)
    else:
        if add:
            dfs(depth+1, num+data[depth], add-1, sub, mul, div)
        if sub:
            dfs(depth+1, num-data[depth], add, sub-1, mul, div)
        if mul:
            dfs(depth+1, num*data[depth], add, sub, mul-1, div)
        if div:
            dfs(depth+1, int(num/data[depth]), add, sub, mul, div-1)

dfs(1, data[0], add, sub, mul, div)

print(max_value)
print(min_value)