백준 #14888 - 연산자 끼워넣기 : 재귀

(python3)

여러 풀이법이 있겠지만, 매 트라이얼에 같은 행위를 반복하고, 이전 행위들이 다음 행위에 영향을 주기 때문에 재귀로 해결했습니다.

4가지 연산자를 함수화하고 함수를 배열에 담아 접근하여 연산자별 사용 횟수 카운팅 처리와 연산 구현을 같은 인덱스로 처리할 수 있게 하여 좀 더 원활히 코드를 작성할 수 있도록 했습니다.

재귀를 사용할 때는 하나의 층에서 변하면 안되지만, 다음 층으로는 변화시켜 넘겨야할 변수들은 새롭게 할당하여 처리하고, 자료구조의 경우 copy 메서드를적절히 사용해주어야 의도치 않은 에러를 피할 수 있습니다.

 

구현 코드

# https://www.acmicpc.net/source/60887220
# 23.05.17 8:51 AM!
def solution(input) : 
    def plus(a,b) :
        return a+b
    def minus(a,b) :
        return a-b
    def multi(a,b) :
        return a*b
    def divi(a,b) :
        if a<0 :
            return -((-a)//b)
        else :
            return a//b
    oper = [plus, minus, multi, divi]
    
    N = int(input())
    num = list(map(int,input().split()))
    oper_max_cnt = list(map(int, input().split()))
    global cal_f
    cal_f = []
    def recur(i, cal, cnt) : # i : 현재 연산해야하는 인덱스 번호 (0~N-1)
        global cal_f
        if i >= N :
            cal_f.append(cal)
            return
        for o in range(4) :
            ncnt = cnt.copy()
            if ncnt[o] < oper_max_cnt[o] :
                ncnt[o]+=1
                ncal = oper[o](cal, num[i])
                recur(i+1, ncal, ncnt)
    
    recur(1,num[0],[0,0,0,0])
    print(max(cal_f))
    print(min(cal_f))

solution(input)