BAEKJOON-14888 : 연산자 끼워넣기

BEAKJOON-14888 : 연산자 끼워넣기

입력받고 리스트로 바꿔주지 않은 덕분에 오류에 허덕여 오래걸렸지만,

문제 푸는 시간 자체는 조금 걸린 문제였다.

백트랙킹 알고리즘으로 풀으니 쉽게 풀리는 문제였다.

다만 조심해야할 건 나누기 연산이었다.

나누기 연산의 결과 값이 음의 실수이면 내림을 해서 양수와 다른 결과가 나온다.

예를 들어 -1.3이면 -2가 되고, 1.3이면 1이 된다. 이 부분만 조심하면 된다.

코드

from math import trunc
n = int(input())
numbers = list(map(int,input().split()))
operations = list(map(int, input().split()))
opIdx = ['+','-','*','/']
minV = []
maxV = []

def calculate(a, op, b):
    if op == '+':
        return a+b
    elif op == '-':
        return a-b
    elif op == '*':
        return a*b
    else:
        return trunc(a/b)

def dfs(depth):
    global minV
    global maxV
    if depth == n-1:
        if not minV:
            minV.append(numbers[n-1])
            maxV.append(numbers[n-1])
        else:
            minV[0] = min(minV[0], numbers[n-1])
            maxV[0] = max(maxV[0], numbers[n-1])
        return
    
    for i in range(4):
        if operations[i] != 0:
            operations[i] -= 1
            origin = numbers[depth+1]
            numbers[depth+1] = calculate(numbers[depth],opIdx[i],numbers[depth+1])
            dfs(depth+1)
            operations[i] += 1
            numbers[depth+1] = origin

dfs(0)
print(maxV[0], minV[0])

각 연산 기호의 개수를 담은 배열operations을 순회하여 기호 하나씩 계산하여 다음 인덱스에 넣는다.

다음 인덱스에 넣기 전에 원래 값을 저장하여 다음 깊이의 dfs를 돌고 난 후 다시 다음 인덱스의 원래 값을 넣어준다.

깊이가 n-1이면 numbers배열 끝까지 계산했다는 뜻이므로, max값과 min값을 갱신하고 return한다.