[백준] 14888 - 연산자 끼워넣기 (Python)

문제 링크

문제

N개의 수열과 N-1개의 연산자가 주어짐
이것들을 조합해서 만들 수 있는 최댓값과 최솟값을 출력하는 문제
단, 수열의 순서를 바꿀 수 없다.

알고리즘

브루투포스 알고리즘
백트래킹

입력

첫째 줄에 수의 개수 N(2 ≤ N ≤ 11) 가 주어진다.
둘째 줄에는 A1, A2, ..., AN 이 주어진다. (1 ≤ Ai ≤ 100)
셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데,
차례대로 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)의 개수이다.

출력

첫째 줄에 만들 수 있는 식의 결과의 최댓값을, 둘째 줄에는 최솟값을 출력한다.
중간 결과값, 최종 결과값이 10억, -10억을 넘지 않는다.
우선 연산자는 신경쓰지 않는다.

입력 예

6
1 2 3 4 5 6
2 1 1 1

출력 예

54
-24

입출력 예에 대한 설명

• 최댓값 : 1-2÷3+4+5×6 = 54
• 최솟값 : 1+2+3÷4-5×6 = -24
  
  

나의 풀이

나는 순열을 이용해서 문제를 해결했다.
예를 들어 연산자가 2 1 1 1 로 들어오면
['+','+','-','*','/'] 형태로 변환한다.
그리고 변환된 리스트를 하나하나 순서를 바꿔가며 최댓값, 최솟값과 비교한다.
브루투포스 알고리즘을 사용한 이 방법은 속도가 느려서 Python3 에선 통과되지 않고 PyPy3 에서 통과된다.

순열

from itertools import permutations
import sys

# ex) [1,2,3,4], ['+','-','/'] 형식의 매개변수가 주어지면 계산값을 반환하는 함수
def calculator(nums, operators):
    res = nums[0]
    for i in range(len(operators)):
        if operators[i] == "+":
            res += nums[i + 1]
        elif operators[i] == "-":
            res -= nums[i + 1]
        elif operators[i] == "*":
            res *= nums[i + 1]
        else:
            if res >= 0:
                res //= nums[i + 1]
            else:
                res = -res // nums[i + 1]
                res = -res
    return res


input = sys.stdin.readline

N = int(input())
nums = list(map(int, input().split()))

# 주어진 숫자를 연산자로 변환
operators_input = list(map(int, input().split()))
operators_def = ["+", "-", "*", "/"]
operators = []
for i in range(4):
    for _ in range(operators_input[i]):
        operators.append(operators_def[i])

max_num = -1e9
min_num = 1e9

# 순열을 하나하나 순회하면서 max_num, min_num과 비교
for combi in permutations(operators):
    new_num = calculator(nums, combi)
    max_num = max([new_num, max_num])
    min_num = min([new_num, min_num])
print(max_num)
print(min_num)

더 좋은 풀이

출처 - kimdukbae
순열보다 백트래킹 (DFS) 을 이용한 방법이 더 빠르다.
백트래킹은 재귀함수를 이용한 방법이다.
Python3, PyPy3 둘다 통과 가능하다.

백트래킹

import sys

input = sys.stdin.readline
N = int(input())
num = list(map(int, input().split()))
operators = list(map(int, input().split()))

max_num = -1e9
min_num = 1e9


# +,-,*,/ 모든 경우의수에서 동시다발적으로 재귀함수 호출
# 단계를 지날 때마다 total값 누적
# 만약 숫자들을 모두 순회하면 최댓값,최솟값 비교

def dfs(depth, total, plus, minus, multiply, divide):
    global max_num, min_num
    if depth == N:
        max_num = max(total, max_num)
        min_num = min(total, min_num)
        return

    if plus:
        dfs(depth + 1, total + num[depth], plus - 1, minus, multiply, divide)
    if minus:
        dfs(depth + 1, total - num[depth], plus, minus - 1, multiply, divide)
    if multiply:
        dfs(depth + 1, total * num[depth], plus, minus, multiply - 1, divide)
    if divide:
        dfs(depth + 1, int(total / num[depth]), plus, minus, multiply, divide - 1)


dfs(1, num[0], operators[0], operators[1], operators[2], operators[3])
print(max_num)
print(min_num)