풀이
수열이 주어지고 사용할 수 있는 연산자들이 주어졌을 때 최대와 최소값을 구하는 문제이다.
수열의 순서를 변경할 수 없기 때문에 DFS 개념을 활용하여 주어진 연산자들에 관한 모든 경우의 수를 통해 최대와 최소값을 찾는다.
재귀를 활용하여 최대 재귀까지 진입했을 때 최대와 최소값을 업데이트해주고 재귀를 진입할 때 네가지 연산자에 대한 연산을 모두 해준 뒤 전달한다.
DFS 수행이 끝난 후 최대와 최소값을 출력해준다.
소스코드
# 연산자 끼워넣기 (2)
import sys
input = sys.stdin.readline
n = int(input())
nums = list(map(int, input().split()))
oper = list(map(int, input().split()))
mx, mn = -1e9, 1e9
def dfs(idx, ans, add, sub, mul, div):
global mx, mn
if idx == n:
mx = max(mx, ans)
mn = min(mn, ans)
return
if add > 0:
dfs(idx+1, ans+nums[idx], add-1, sub, mul, div)
if sub > 0:
dfs(idx+1, ans-nums[idx], add, sub-1, mul, div)
if mul > 0:
dfs(idx+1, ans*nums[idx], add, sub, mul-1, div)
if div > 0:
dfs(idx+1, ans//nums[idx] if ans > 0 else -((-ans)//nums[idx]), add, sub, mul, div-1)
dfs(1, nums[0], oper[0], oper[1], oper[2], oper[3])
print(mx)
print(mn)