연산자 끼워넣기 [백준 14888]

문제

---

연산자 끼워넣기 [백준 14888]
https://www.acmicpc.net/problem/14888

풀이

---

연산자의 개수와 수열이주어지면 수열 사이에 연산자를 넣어 나오는 최대와 최소를 구하는 문제이다. 이 문제는 두가지 해결법이 있다. itertool에 permutations(순열) 함수를 이용하는 방법과 너비우선탐색을 사용하는 방법이다.

코드

---

# dfs
from itertools import permutations
from sys import stdin
input = stdin.readline

n = int(input())
num_list = list(map(int, input().split()))
cal_list = list(map(int, input().split()))

max_res = -1e9
min_res = 1e9

def dfs(num, p, m, t, d, idx):
   if idx == n - 1:	#마지막 인덱스
       global max_res, min_res
       min_res = min(min_res, num)
       max_res = max(max_res, num)
       
   if p:				#남은 +가 1 이상일때
       dfs(num + num_list[idx + 1], p - 1 , m, t, d, idx + 1)
   if m:				#남은 -가 1 이상일때
       dfs(num - num_list[idx + 1], p , m - 1, t, d, idx + 1)
   if t:				#남은 *가 1 이상일때
       dfs(num * num_list[idx + 1], p , m, t - 1, d, idx + 1)
   if d:				#남은 /가 1 이상일때
       dfs(int(num / num_list[idx + 1]), p , m, t, d - 1, idx + 1)

dfs(num_list[0], cal_list[0], cal_list[1], cal_list[2], cal_list[3], 0)
print(max_res)
print(min_res)