백준 14888번: 연산자 끼워넣기 (Python, PyPy3)

접근

각 숫자들 사이를 빈칸이라고 두고, 해당 칸에 들어갈 수 있는 연산자를 넣어보면서 해당 숫자들과 연산자들로 얻을 수 있는 가장 큰 수와 작은 수를 구하는 백트래킹 문제이다.

사용할 수 있는 연산자들을 모두 list에 모아두고, 해당 연산자가 사용되었는지를 저장하는 또 한개의 list를 이용하였다. 중간에 temp라는 이름의 list를 이용하여 계산이 완료된 후 되돌아갈 중간 값들을 저장해주었다.

다시 풀기(2022.9.19)

백트래킹 문제였습니다.

덧셈, 뺄셈, 곱셈, 나눗셈에 대한 함수를 만들어 배열에 저장해주고, 백트래킹 알고리즘을 이용하여 처음 숫자부터 순서대로 계산하면서 depth 가 마지막에 도달하면 최대값과 최소값을 갱신해줍니다.

매 depth 마다 사칙연산 4가지를 고려하고, 해당 사칙연산의 남은 갯수가 0보다 크다면 해당 부호를 이용하고 값을 다음 계산에 넘겨줍니다.

주의할점은 최대값의 초기값을 0이 아닌 음의 무한대로 지정해야 한다는 점입니다. 이 점을 고려하지 않고 0으로 둔다면 1%에서 오답을 받게 됩니다.

코드

새로 작성한 코드: 훨씬 단순하고 직관적입니다.

N = int(input())
arr = list(map(int, input().split(" ")))
op_num = list(map(int, input().split(" ")))
minVal = float("inf")
maxVal = -float("inf")


def plus(a, b):
    return a + b


def minus(a, b):
    return a - b


def multiply(a, b):
    return a * b


def divide(a, b):
    if a < 0:
        return -(-a // b)
    else:
        return a // b


op_arr = [plus, minus, multiply, divide]


def dfs(idx, value):
    global minVal, maxVal
    if idx == N - 1:
        minVal = min(minVal, value)
        maxVal = max(maxVal, value)
        return

    for i in range(4):
        if op_num[i] > 0:
            op_num[i] -= 1
            dfs(idx + 1, op_arr[i](value, arr[idx + 1]))
            op_num[i] += 1


dfs(0, arr[0])
print(maxVal)
print(minVal)

이전 코드

import sys

n = int(sys.stdin.readline())
number_list = list(map(int, sys.stdin.readline().split()))
a, b, c, d = map(int, sys.stdin.readline().split())
cal_list = ['+' for i in range(a)] + ['-' for j in range(b)] + ['*' for k in range(c)] + ['/' for l in range(d)]
cal_used = [False for x in range(len(cal_list))]
ans = []
temp = [number_list[0]]


def calculate(e, g, f):
    if g == '+':
        return e + f
    elif g == '-':
        return e - f
    elif g == '*':
        return e * f
    else:
        if e * f < 0:
            return -((-e) // f)
        return e // f


def mix(x):
    if x == len(cal_list):
        ans.append(temp[x])
        return
    for i in range(len(cal_list)):
        if cal_used[i]:
            continue
        cal_used[i] = True
        result = calculate(temp[x], cal_list[i], number_list[x + 1])
        temp.append(result)
        mix(x + 1)
        temp.pop()
        cal_used[i] = False


mix(0)
print(max(ans))
print(min(ans))

더 생각해 볼 것?

이 문제 또한 백트래킹 문제인데 Python으로는 시간안에 들어오지 못해 PyPy3을 이용하여 통과하였다.
더 최적화 할 수 있는 구간이 있는지..?

(제시된 코드가 가장 최적의 코드가 아님을 참고해주세요. 지적 및 조언 환영합니다~)