[PS] BOJ 14888 / 연산자 끼워넣기

Minjun Kim

22 Sep 2025 • 2 min read

Thumbnail: Photo by Second Breakfast (Unsplash)

문제 링크: https://www.acmicpc.net/problem/14888

백트래킹으로 수식을 완성해 나가는 문제입니다.

풀이

수열 사이에 연산자 채우기

입력으로 주어지는 수열 $A$의 각 수 사이에 +, -, $\times$, $\div$의 4가지 연산자를 임의로 채울 때, 전체 수식의 결과값의 최댓값과 최솟값을 구하는 문제입니다.

단, 각각의 연산자는 사용해야 하는 개수가 정해져 있습니다. $2 \leq N \leq 11$이므로 백트래킹을 통해 구현할 수 있습니다.

주의해야 할 사항들

1) 연산 순서

이 문제에서 수식을 계산하는 방법은 흔히 아는 연산자 우선순위를 무시한 채 그냥 앞에서부터 순서대로 계산합니다.

따라서, 백트래킹을 진행하면서 바로바로 연산을 진행할 수 있습니다.

2) 나눗셈의 구현 방식

이 문제에서 나눗셈은 정수 나눗셈으로, 나눗셈의 몫만 취합니다. 이 때, 음수를 양수로 나눌 때는 양수로 바꾼 뒤 몫을 취하고, 그 결과를 다시 음수로 만듭니다.

Python3의 경우, 정수 나눗셈 연산자 (//, truediv)가 있지만, 이 연산자의 동작은 문제에서 요구하는 방식과 다릅니다.

def div(l, r):
    """문제에서 요구하는 정수 나눗셈을 구현한 함수"""
    negative = False
    if l < 0:
        negative = True
    if r < 0:
        negative = not negative
    l = abs(l) // abs(r)
    if negative:
        l *= -1
    return l

문제 조건에 맞는 정수 나눗셈 구현

전체 코드

input = open(0).readline
N = int(input())
A = list(map(int, input().split()))
OP_LIMIT = list(map(int, input().split()))
max_value = -1_000_000_001
min_value = 1_000_000_001

def div(l, r):
    negative = False
    if l < 0:
        negative = True
    if r < 0:
        negative = not negative
    l = abs(l) // abs(r)
    if negative:
        l *= -1
    return l

OPS = ((0, lambda l, r: l + r), (1, lambda l, r: l - r), (2, lambda l, r: l * r), (3, div))

def backtrack(depth, expr_result):
    if depth == N - 1:
        global max_value, min_value
        max_value = max(expr_result, max_value)
        min_value = min(expr_result, min_value)
        return
    
    for op_idx, op_func in OPS:
        if OP_LIMIT[op_idx] > 0:
            OP_LIMIT[op_idx] -= 1
            backtrack(depth + 1, op_func(expr_result, A[depth + 1]))
            OP_LIMIT[op_idx] += 1

backtrack(0, A[0])
print(f"{max_value}\n{min_value}")

solution.py