[백준/Python] 14888번 : 연산자 끼워넣기

N개의 수와 N-1개의 연산자가 주어졌을 때, 만들 수 있는 식의 결과가 최대인 것과 최소인 것을 각각 구하는 프로그램이다.

단순한 사칙연산을 계속 반복하는데, 연산자(+,-,*,//)들이 담긴 queue들이 눈 앞에 아른거린다면 bfs를 고려해봐야한다. 너비 탐색은 queue나 재귀함수로 구현할 수 있는데, 재귀함수로 구현하는 편이 더 쉬울 것 같아서 택하게 되었다.

숫자 연산은 1+2+3 이런 식일 때, (1+2)+3 = (3+3) =6 이렇듯이 앞 쪽부터 두 개의 피연산자씩 묶어서, 다음 함수로 전달할 때는 결과값과 '이번이 마지막 연산이었다'를 알리기 위한 index를 전달해줘야 한다. 또한 숫자열은 사용되는 순서가 항상 같으므로 index를 통해 숫자열 안의 숫자들을 차례대로 연산해나간다. 마지막 결과값과 연산할 그 다음 피연산자가 없기 때문에 확실시해야하는 것이다.

재귀함수 내부에서 더하기, 빼기, 곱하기, 나누기 연산자가 남아있을 각각의 경우를 가정하면 알아서 모든 연산자들을 사용할 때까지의 연산을 수행한다.

#N개의 수와 N-1개의 연산자가 주어졌을 때, 만들 수 있는 식의 결과가 최대인 것과 최소인 것
import sys
n=int(input()) #숫자의 개수
a=[]
a.extend(list(map(int,input().split())))
p,m,mul,div=map(int,input().split())
minn=sys.maxsize
maxn=-sys.maxsize-1
def cal(num,index,plus,minus,mul,div): #계산결과,몇 번째 숫자와의 계산이었는지, 사용할 수 있는 연산자 개수 몇 개 남았는지
    global minn,maxn
    if index==n:#방금 연산에 사용한 것이 마지막 원소였을 때
        maxn=max(num,maxn) #최댓값 구함
        minn=min(num,minn) #최솟값 구함
        return #종료
    else:
        if plus: #아직 plus연산자가 남아있을 때
            cal(num+a[index],index+1,plus-1,minus,mul,div)
        if minus: #아직 minus연산자가 남아있을 때
            cal(num-a[index],index+1,plus,minus-1,mul,div)
        if mul: #아직 mul연산자가 남아있을 때
            cal(num*a[index],index+1,plus,minus,mul-1,div)
        if div: #아직 div연산자가 남아있을 때
            cal(int(num/a[index]),index+1,plus,minus,mul,div-1)
       
cal(a[0],1,p,m,mul,div) #첫번째 숫자와 두번째 숫자(인덱스1)의 연산
print(maxn)
print(minn)