[실버1] 14888번 : 연산자 끼워넣기

🛠 문제

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

👩🏻‍💻 해결 방법

전형적인 백트래킹 문제로 처음에는 풀기 어려웠다...
덧셈, 뺄셈, 곱셈, 나눗셈 모두 갯수만큼 dfs를 호출하고, n개의 수를 썼을 경우 최솟값과 최댓값을 갱신해주었다

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

min_val = 1e9
max_val = -1e9

def dfs(i, now):
  global min_val, max_val, add, sub, mul, div

  if i == n:
    min_val = min(min_val, now)
    max_val = max(max_val, now)
  else:
    if add > 0:
      add -= 1
      dfs(i + 1, now + nums[i])
      add += 1
    if sub > 0:
      sub -= 1
      dfs(i + 1, now - nums[i])
      sub += 1
    if mul > 0:
      mul -= 1
      dfs(i + 1, now * nums[i])
      mul += 1
    if div > 0:
      div -= 1
      dfs(i + 1, int(now / nums[i]))
      div += 1

dfs(1, nums[0])

print(max_val)
print(min_val)