[백준] 15658번 연산자 끼워넣기 (2) (Python)

풀이

---

수열이 주어지고 사용할 수 있는 연산자들이 주어졌을 때 최대와 최소값을 구하는 문제이다.

수열의 순서를 변경할 수 없기 때문에 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)

References

---

• BOJ 15658 - 연산자 끼워넣기 (2)