브루트포스) 15658.연산자 끼워넣기(2)

Carnival7 2022. 6. 7. 18:23

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

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

N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다. 연산자의 개수

www.acmicpc.net

n=int(input())

nums=list(map(int,input().split()))

ops = list(map(int,input().split()))

max_ans=-1000000001
min_ans=10000000001

def dfs(index,s):
    global max_ans,min_ans
    # 종료 조건
    if index==n:
        # if s>=max_ans:
        #     max_ans=s
        # if s<=min_ans:
        #     min_ans=s
        max_ans = max(s,max_ans)
        min_ans = min(s,min_ans)
        return
    if index>n:
        return

    # 더하기
    if ops[0] > 0:
        ops[0]-=1
        dfs(index+1,s+nums[index])
        ops[0]+=1
    # 빼기
    if ops[1] > 0:
        ops[1]-=1
        dfs(index+1,s-nums[index])
        ops[1]+=1
    # 곱하기
    if ops[2] >0:
        ops[2]-=1
        dfs(index+1,s*nums[index])
        ops[2]+=1
    # 나누기
    if ops[3]>0 :
        ops[3]-=1
        if s<0:
            s=-s
            s//=nums[index]
            s=-s
        else:
            s//=nums[index]
        dfs(index+1,s)
        ops[3]+=1

dfs(1,nums[0])

print(max_ans)
print(min_ans)