[Algorithm] 백준 14888 연산자 끼워넣기 python

백준 14888 연산자 끼워넣기 원문

문제가 뭐지?

N개의 수로 이루어진 수열이 주어지고, 그 사이 사이에 끼워 넣을 수 있는 연산자가 n-1개 주어진다. 연산자는 +,-,x,/ 로만 이루어져있다.

가령, 1,2,3,4,5,6의 6개의 수열이 주어지고, +가 2개, -가 1개, x가 1개, /가 1개 주어지는 경우 총 60가지의 식을 만들 수 있단다나..

문제는 주어지는 수열에다가 주어진 갯수의 연산자들을 잘 분배해서 넣었을 때, 식의 결과가 최대인 것과 최소인 것을 구하는 것이다.

어떻게 풀었지?

모든 식을 다 봐야 하니까 완전탐색이라고 생각을 했다. 여러가지가 떠오르긴 했지만, 가장 먼저 생각 난 것은 재귀로 돌리는 것이다. 주어진 수열의 끝까지 갔을 때 해서 최소값 최대값을 갱신하고 끝내는 재귀로 돌린다. 완전탐색이니만큼 연산자를 쓰는 경우 안 쓰는 경우를 생각을 해야 한다. for문으로 연산자 배열을 처음부터 돌린다. 쓰는 경우, 다음 for문에서는 이전 값은 사용되지 않았어야 했기 때문에, 감소한 배열에 deepcopy를 다음 재귀의 인자로 넘겼다.

어디서 헤맸지?

문제 조건을 보면 "또, 나눗셈은 정수 나눗셈으로 몫만 취한다. 음수를 양수로 나눌 때는 C++14의 기준을 따른다."

라고 한다.. 나는 operation 함수를 따로 정의해서 문자열 연산자를 입력받으면 계산을 하게 했는데 계속 답이 틀리길래 뭐가 문젤까 하다가 저걸 그대로 옮겼더니 답이 맞았다..

코드

import sys
from copy import deepcopy
"""
op = ["+","-","*","/"]
"""
op = ["+","-","*","/"]

max = float("-inf")
min = float("inf")

def do_operation(ope,val1, val2) :
    if ope == "+" :
        return val1+val2
    elif ope == "-" :
        return val1-val2
    elif ope =="*" :
        return val1*val2
    elif ope == "/" :
        if val1 < 0 :
            val1 = -(val1)
            return -(val1//val2)
        else :
            return val1//val2 


def dfs(n,a,operators,idx,sum) :
    global max,min

    if idx == n :
        if max < sum :
            max = sum
        if min > sum :
            min = sum
        return
        
    for i in range(4) :
        copied_operators = deepcopy(operators)
        if copied_operators[i] > 0  :
            copied_operators[i] -= 1
            dfs(n,a,copied_operators,idx+1,do_operation(op[i],sum,a[idx]))
            
def solve() :
    n = int(sys.stdin.readline())
    a = list(map(int,sys.stdin.readline().split()))
    operators = list(map(int,sys.stdin.readline().split()))

    dfs(n,a,operators,1,a[0])

    print(max)
    print(min)



if __name__ == "__main__" :
    solve()

생각해보니까 전에 for문에서 dfs로 삽질하던거 이거랑 똑같은 것 같은데 이거 먼저 풀었는데 왜그랬지