[백준][알고리즘] 14888 연산자 끼워넣기

def plus(a,b):
    return a+b
def minus(a,b):
    return a-b
def multi(a,b):
    return a*b
def div(a,b):
    if a <0:
        a = -a
        ans = -(a//b)
    else:
        ans = (a//b)
    return ans
N = int(input())
numlist = list(map(int,input().split()))
count = list(map(int,input().split()))
lit = []
for i in range(count[0]):
    lit.append("+")
for i in range(count[1]):
    lit.append("-")
for i in range(count[2]):
    lit.append("*")
for i in range(count[3]):
    lit.append("%")

visited = [False]*(N-1)
def permu(lit,idx,visited,stack):
    global total
    if idx == N-1:
        total = numlist[0]
        for i in range(0,N-1):
            if stack[i] == "+":
                total = plus(total,numlist[i+1])
            if stack[i] == "-":
                total = minus(total,numlist[i+1])
            if stack[i] == "*":
                total =multi(total,numlist[i+1])
            if stack[i] == "%":
                total = div(total,numlist[i+1])
        anss.append(total)
    for i in range(0,N-1): #N-1개
        if visited[i] == False:
            visited[i] = True
            stack.append(lit[i])
            permu(lit,idx+1,visited,stack)
            visited[i] = False
            stack.pop()
anss = []
permu(lit,0,visited,[])
print(max(anss))
print(min(anss))

1. 재귀함수 OR itertools로 연산자 순열 구하기(나는 재귀함수 활용)

2. 구해진 순열로 하나씩 연산 

잘 이용한거 같지만.... 시간초과다^^

브루스포트의 문제 대부분이 순열/조합 을 활용하여 그 위에 무언가 작업을 하는 형태이다.

그런데 풀기는 하지만 모두 시간초과가 난다....

 

 

-----------------------------------------------2021 - 1 - 12 풀이 --------------------------------------------------------

코드가 그래도 정리가 이전보다 잘된것 같다

마찬가지로 조합을 활용한다. -> 이전 문제의 방식을 응용을 통해서 재귀함수가 상당히 깔끔해졌다.

리스트를 만드는 방식, enumerate 또한 적절히 잘 활용했다. 

num = int(input())
numlist = list(map(int,input().split()))
calu = list(map(int,input().split()))
mx = -10**9
mn = 10**9
# 가능한 조합 생성 하기
calu_t = calu[0] * "+" + calu[1] * "-" + calu[2] * "*" + calu[3] * "/"
check = [False] * (num-1)
# 조합을 계산해서 결과 전달하기

def cal(s):
    ans = numlist[0]
    for index,signal in enumerate(s):
        if signal == "+":
            ans += numlist[index+1]
        elif signal == "-":
            ans -= numlist[index+1]
        elif signal == "*":
            ans *= numlist[index+1]
        elif signal == "/":
            #음수 나누기 연산 조심

            if ans > 0:
                ans = int(ans / numlist[index+1])
            else:
                ans = -ans
                ans = int(ans / numlist[index + 1])
                ans = -ans
    return ans


def recu(cnt, s):
    global mx, mn
    if len(s) == num-1:
        tem = cal(s)
        if tem > mx:
            mx = tem
        if tem < mn:
            mn = tem

    for i in range(num-1): #num-1 개의 부등호가 존재한다
        if check[i] == False:
            check[i] = True
            recu(cnt+1, s+calu_t[i])
            check[i] = False

    return

recu(0,"")
print(mx)
print(mn)