[백준/Python] 14888번 : 연산자 끼워넣기

문제

문제

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

---

Algorithm

최대, 최소 정답을 미리 설정 후 dfs 함수를 통해 백트래킹을 진행한다.
idx가 목표값에 도달하면 결과를 비교후 저장하고 dfs함수가 끝나면 정답을 출력한다.

 

---

 

 

Code

n = int(input())
number = list(map(int, input().split()))
add, sub, mul, div = map(int, input().split())
max_result = - int(1e9)
min_result = int(1e9)

def dfs(add, sub, mul, div, sum, idx):
    global max_result, min_result
    if idx == n:
        max_result = max(max_result, sum)
        min_result = min(min_result, sum)
        return
    if add:
        dfs(add-1, sub, mul, div, sum + number[idx], idx + 1)
    if sub:
        dfs(add, sub-1, mul, div, sum - number[idx], idx + 1)
    if mul:
        dfs(add, sub, mul-1, div, sum * number[idx], idx + 1)
    if div:
        dfs(add, sub, mul, div-1, int(sum / number[idx]), idx + 1)
        
dfs(add, sub, mul, div, number[0], 1)
print(max_result)
print(min_result)