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

문제

---

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

15658번: 연산자 끼워넣기 (2)

 

생각의 흐름

---

 

이전에 포스팅한 연산자 끼워넣기와의 차이점은 연산자의 갯수가 많아졌다는 점이다.

동일한 방법으로 짜도 정답은 맞지만 시간초과가 난다는 사실...

아마 연산자 갯수가 많아졌는데 이들을 permutations에 넣고 돌리는 부분에서 시간 초과가 난 듯하다.

이를 개선하기 위해 재귀를 이용하였다.

 

 

코드

---

n = int(input())
a = list(map(int, input().split()))
op = list(map(int, input().split()))
mx, mn = -1e9, 1e9 # 최대 최소 처음 수

def solve(index, ans, add, sub, mul, div) :
    global mx, mn
    if index >= n :
        mx = max(mx, ans)
        mn = min(mn, ans)
        return
    if add > 0 :
        solve(index+1, ans+a[index], add-1, sub, mul, div)
    if sub > 0 :
        solve(index+1, ans-a[index], add, sub-1, mul, div)
    if mul > 0 :
        solve(index+1, ans*a[index], add, sub, mul-1, div)
    if div > 0 :
        solve(index+1, ans//a[index] if ans > 0 else -((-ans)//a[index]), add, sub, mul, div-1)

solve(1, a[0], op[0], op[1], op[2], op[3])
print(mx)
print(mn)

### 출처 : https://statssy.github.io/pro/2019/09/11/baekjoon_15658/