[BFS/DFS] 백준 14888번 '연산자 끼워넣기' (Python)

<문제 링크>

https://www.acmicpc.net/problem/14888

14888번: 연산자 끼워넣기

---

<문제 풀이>

1. 연산을 할 함수를 만든다.

2. 입력값 수만큼 각 연산으로 바꾸고 조합을 만든다.

3. 1번에서 만든 함수를 반복하여 최댓값, 최솟값을 찾는다.

 

<코드>

#220328
from itertools import permutations

def op(a,b,opp):
    if opp=='+':
        return a+b
    elif opp=='-':
        return a-b
    elif opp=='*':
        return a*b
    elif opp=='/':
        return int(a/b)

n = int(input())
alist = list(map(int,input().split()))
option = list(map(int,input().split()))

pm = []

for idx, i in enumerate(option):
    for j in range(i):
        if idx==0:
            pm.append('+')
        elif idx==1:
            pm.append('-')
        elif idx==2:
            pm.append("*")
        elif idx==3:
            pm.append('/')

per = set(permutations(pm,n-1))

minn = 1e9
maxx = -1e9

for perpm in per:
    tmp = alist[0]
    for a,p in zip(alist[1:],perpm):
        tmp = op(tmp,a,p)
    if tmp < minn:
        minn = tmp
    if tmp > maxx:
        maxx = tmp

print(maxx)
print(minn)