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

백준 #14888 Level : 💣

---

✍Logic

N개의 정수로 이루어진 수열과 N-1개의 연산자가 주어진다.

수와 수 사이에 연산자를 하나씩 넣어서 수식을 만들고, 만들 수 있는 수식 결과의 최댓값과 최솟값을 구하는 문제이며, 아래와 같은 솔루션으로 문제를 해결했다.

[1] permutations() 함수를 이용하여, 먼저 연산자 순열을 만든다.  

[2] 그렇게 만들어진 수식의 결과를 받아 최댓값과 최솟값을 구한다.   <br>

---

💻Code

from itertools import permutations

def calculator(operator, num1, num2):  # 계산 함수
    if operator == "+":`
        return num1 + num2
    elif operator == "-":
        return num1 - num2
    elif operator == "*":
        return num1 * num2
    else:
        if num1 < 0:
            return -(abs(num1) // num2)
        else:
            return num1 // num2

n = int(input())
nums = list(map(int, input().split()))  # 숫자열
cnt = list(map(int, input().split()))   # 연산자별 개수
cal = ["+", "-", "*", "/"]

# operators: n-1개의 연산자 리스트
operators = []
temp = ''
for i in range(4):
    if cal[i] * cnt[i]:
        temp += cal[i] * cnt[i]
operators = list(temp)

# [1] operators로 순열 만들기
permute = list(permutations(operators, n-1))

# [2] 계산하기
max_, min_ = -1e9, 1e9
res = nums[0]
for i in range(len(permute)):
    for j in range(n-1):
        res = calculator(permute[i][j], res, nums[j+1])
    # 계산 끝나면?
    max_ = max(max_, res)
    min_ = min(min_, res)
    res = nums[0]

print(max_, min_, sep='\n')

🙋‍♀️REF

(thx to Jupearl)

문제를 풀고 Jupearl의 코드를 보며, DFS로도 해당 문제를 풀 수 있다는 것을 알았다.

솔루션은 아래와 같다.

DFS 매서드 함수에 입력받은 수열의 개수 만큼 계속 반복해서 재귀적으로 계산한다.   <br>

필자는 실행시간 2788ms가 걸렸고, Jupearl은 324ms만 걸렸다.

즉, DFS를 사용하는 방법이 순열보다 시간복잡도가 훨씬 낮다는걸 알 수 있었으며, 아래에 Jupearl의 DFS 코드를 소개하겠다.

cal_dict = {
    0:lambda x, y : x + y,
    1:lambda x, y : x - y,
    2:lambda x, y : x * y,
    3:lambda x, y : int(x / y)
}

def DFS(num_list):
    global cal, res, min_res, max_res
    if len(num_list) == 1:
        if num_list[0] <= min_res:
            min_res = num_list[0]
        if num_list[0] >= max_res:
            max_res = num_list[0]
        return
    
    for idx in range(4):
        if cal[idx]:
            cal[idx] -= 1
            x, y = num_list.pop(0), num_list.pop(0)
            res = cal_dict[idx](x, y)
            DFS([res]+num_list)
            cal[idx] += 1
            res -= cal_dict[idx](x, y)
            num_list = [x, y] + num_list


N = int(input())
num_list = list(map(int,input().split()))
cal = list(map(int,input().split()))

min_res = 10**22
max_res = -10**22
res = 0
DFS(num_list)
print(max_res)
print(min_res)