백준(Python) 14888번 연산자 끼워넣기 풀이

Python으로 구현한 14888번 연산자 끼워넣기 문제 풀이입니다.

 

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

14888번: 연산자 끼워넣기

---

n = int(input())

# 연산을 수행하고자 하는 두 리스트
data = list(map(int, input().split()))
# 더하기, 빼기, 곱하기, 나누기 연산자 개수
add, sub, mul, div = map(int, input().split())

# 최솟값과 최댓값 초기화
min_value = 1e9
max_value = -1e9

# 깊이 우선 탐색(DFS) 메서드
def dfs(i, now) :
  global min_value, max_value, add, sub, mul, div
  # 모든 연산자를 다 사용한 경우, 최솟값과 최댓값 갱신
  if i == n :
    min_value = min(min_value, now)
    max_value = max(max_value, now)
  else :
    # 각 연산자에 대하여 재귀적으로 수행
    if add > 0 :
      add -= 1
      dfs(i + 1, now + data[i])
      add += 1
    if sub > 0 :
      sub -= 1
      dfs(i + 1, now - data[i])
      sub += 1
    if mul > 0 :
      mul -= 1
      dfs(i + 1, now * data[i])
      mul += 1
    if div > 0 :
      div -= 1
      dfs(i + 1, int(now / data[i]))
      div += 1

# DFS 메서드 호출
dfs(1, data[0])

# 최댓값과 최솟값 출력
print(max_value)
print(min_value)