백준_괄호 추가하기(#16637)_파이썬(python)_ 삼성기출

어려웠던 점

괄호를 넣는 총 경우의 수를 계산하는 것이 힘들었다.(코드에서 recur 함수)

재귀를 더 공부해야겠다.

 

def recur(seq,score,op):

괄호를 넣는 순간 2개의 숫자를 소비한다는 개념으로 코딩했다.

그래서 괄호는 't' 괄호 아닌것은 'f' 이다.

seq는 재귀를 위해 전에 것을 저장하는것

score는 현재 소비한 숫자의 갯수

op는 목표 소비 숫자의 갯수이다.

 

질문하면 취뽀 쌉가능.

 

아래 코드는 맘대로 쓰세요.

def repakage(case_dict,num_list, sym_list):
    find_max = -2**31
    for i in case_dict.keys():
        temp_num = num_list[:]
        temp_sym = sym_list[:]
        now = 0
        for j in range(len(i)):
            if i[j] == 't':
                in_put = calculate(temp_num[now:now+2],temp_sym[now:now+1])
                del temp_sym[now]
                del temp_num[now:now+2]
                temp_num.insert(now,in_put)
                now+= 1
            else:
                now+=1
        answer = calculate(temp_num, temp_sym)
        if find_max < answer:
            find_max = answer
    return find_max
 
def recur(seq,score,op):
    if score < op:
        temp = score
        temp_seq = seq
        for i in range(2):
            if i== 0:
                seq +='t'
                score += 2
                recur(seq,score,op)
            else:
                temp_seq +='f'
                temp +=1
                recur(temp_seq,temp,op)
    elif score == op:
        case_dict[seq] = 1
        
 
def minus(a,b):
    return a-b
def multi(a,b):
    return a*b
def plus(a,b):
    return a+b
 
def calculate(num_list,sym_list):
    while len(num_list) != 1:
        a = num_list.pop(0)
        b = num_list.pop(0)
        c = sym_list.pop(0)
        d = 0
        if c == '+':
            d = plus(a,b)
        elif c == '*':
            d = multi(a,b)
        elif c == '-':
            d = minus(a,b)
        num_list.insert(0, d)
    return num_list[0]
 
for i in range(2):
    test = input()
num = []
sym = []
 
for i in range(len(test)):
    if i%2 ==0:
        num.append(int(test[i]))
    else:
        sym.append(test[i])
 
case_dict = {}
 
recur('',0,len(num))
 
print(repakage(case_dict, num, sym))