[BOJ] Q14888 연산자 끼워넣기

[BOJ] Q14888 연산자 끼워넣기

Question

Language: Python

Difficulty: Silver 1

해당 문제는 dfs(recursion)으로 풀 수 있다. 각각의 연산자 별로 개수가 정해져있으므로, 각 연산자에 대한 연산자를 수행하며, 해당 연산자의 개수를 다 소모한 경우 다른 연산자를 대입해본다.

예시

plus,minus=5,4
def dfs(count,sub_sum,plus,minus):
    if count == n:
        #최소/최대 처리
        return
    if plus > 0:
        dfs(count+1,sub_sum+=list[count],plus-1,minus)
    if minus > 0:
        dfs(count+1,sub_sum-=list[count],plus,minus-1)

위와 같은 방식으로 재귀방식을 통해 문제를 해결할 수 있다.

Solution

from math import inf

def solution(count,result,add,sub,mul,div):
    if count==n:
        global min_sum,max_sum
        min_sum=min(min_sum,result)
        max_sum=max(max_sum,result)
  
    else:
        if add>0:
            solution(count+1,result+operands[count],add-1,sub,mul,div)
        if sub>0:
            solution(count+1,result-operands[count],add,sub-1,mul,div)
        if mul>0:
            solution(count+1,result*operands[count],add,sub,mul-1,div)
        if div>0:
            solution(count+1,int(result/operands[count]),add,sub,mul,div-1)


n = int(input())
operands = list(map(int, input().split()))
add,sub,mul,div = map(int, input().split())
min_sum = inf
max_sum = -inf

solution(1,operands[0],add,sub,mul,div)

print(max_sum, min_sum, sep="\n")