[백준/14888/파이썬] 연산자 끼워넣기

---

소스코드

from itertools import permutations

N = int(input())

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

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

operstr = ['+', '-',  '*', '//']

max_ans = -999999999

min_ans = 999999999

#           +  -  *  /

oplist = []

for i,op in enumerate(operator):

  for j in range(op):

    oplist.append(operstr[i])

many = list(permutations(oplist,len(oplist)))

def cal(num1,num2, operate):

    if operate == "+":

      return num1+ num2

    elif operate == "-":

      return num1-num2

    elif operate == "*":

      return num1 * num2  

    elif num2 != 0:

      if num1 > 0 :

        return num1//num2

      else :

        return abs(num1)//num2 * -1

for oper in many:

  result = num[0]

  for i,operate in enumerate(oper) :  

    result = cal(result,num[i+1],operate)    

  max_ans= max(max_ans,result)

  min_ans= min(min_ans,result)  

print(max_ans)

print(min_ans)

---

알고리즘

백트래킹을 이용하여 푸는 문제지만 permutation을 이용한 브루트포스로 풀었다! 

물론 시간 초과가 났다... 하지만 (Pypy3에서는 정답이 된다는 점!)

1. 우선 첫번째 for문에서는 연산자 리스트 [2,1,1,1] 를 [+,+,-,*,//]로 바꿔주었다.

2. 연산자로 바뀐 리스트에 대한 모든 경우를 permutations를 통해 구한다.

3. cal함수를 문제의 조건에 맞게 구현하였다.

4. 연잔자 ex) (+,+,-,*,//) 형태의 oper안에서 cal 함수를 사용하는데

 그 결과를 계속 넣어 가면서 진행하였다 

 3 = cal(1,2,+)

 6 = cal(3,3,+) ...

5. 최대 최소를 비교하고 값을 return 하면 된다.

---

DFS를 이용한 알고리즘이다.