BOJ #14888 연산자 끼워넣기 python

💡Github URL

: https://github.com/hansun-hub/2025-algorithm-study/commit/cfb990953606b9ec977e81009aab9f8327169db8

 

💡문제에서 구해야 할 것

문제 조건 :

• N개의 수열이 있고 연산자가 주어지는데 만들 수 있는 결과가 최대인 것과 최소인 것을 구해라

 

💡알고리즘 설계

• 연산자 리스트를 만들고 그 리스트의 순열(permutation)을 구하여 가능한 모든 연산자 배열 만듬
• calculate 함수에서 값을 계산함 _ 특히 나눗셈 계산시 음수 나눗셈, 양수 나눗셈 분기해서 구현해줌

 

💡코드

from itertools import permutations

# 수식 계산 함수
def calculate(numbers, operators):
    result = numbers[0]
    index = 1
    for operator in operators:
        if operator == '+':
            result += numbers[index]
        elif operator == '-':
            result -= numbers[index]
        elif operator == '*':
            result *= numbers[index]
        elif operator == '/':
            # 나눗셈은 정수 나눗셈, C++14의 음수 나눗셈 규칙 적용
            if result < 0:
                result = -(-result // numbers[index])
            else:
                result //= numbers[index]
        index += 1
    return result

# 입력 받기
N = int(input())  # 수의 개수
numbers = list(map(int, input().split()))  # 수열 A1, A2, ..., AN
add, sub, mul, div = map(int, input().split())  # 연산자 개수

# 연산자 리스트 만들기
operators = ['+'] * add + ['-'] * sub + ['*'] * mul + ['/'] * div

# 연산자의 모든 순열을 생성
perm_operators = set(permutations(operators))

# 최댓값과 최솟값 계산
max_result = -float('inf')
min_result = float('inf')

for perm in perm_operators:
    result = calculate(numbers, perm)
    max_result = max(max_result, result)
    min_result = min(min_result, result)

# 결과 출력
print(max_result)
print(min_result)

 

💡시간복잡도

perm_operators = set(permutations(operators))

• 연산자 순열 생성할 때

→ 가능한 연산자들의 모든 순열은 (N-1)! 개 

for perm in perm_operators:
    result = calculate(numbers, perm)
    

• calculate() 함수는 숫자 N개에 대해 N-1 번 수행 → O(n)

• 가능한 연산자 배치가 (n-1)! 개 , 각 배치에 대해 o(n) 시간 연산 수행함
• 최종 시간 복잡도는 O((N−1)!×N)
• → n이 커질수록 급격히 느려짐

 

💡 다른 풀이 or 기억할정보

• 지금 내 코드는 모든 연산자의 순열을 구하는 비효율 적임 → 가장 직관적이긴 함
• 백트래킹 이용한 DFS 탐색하면 더 효율적
• → 연산자를 하나씩 선택하면서 탐색, 연산자를 사용할 때마다 개수 줄이기

import sys

# 백트래킹을 이용한 DFS 탐색
def dfs(index, current_result, add, sub, mul, div):
    global max_result, min_result
    
    # 모든 연산자를 사용한 경우, 최댓값과 최솟값 업데이트
    if index == N:
        max_result = max(max_result, current_result)
        min_result = min(min_result, current_result)
        return
    
    # 덧셈
    if add > 0:
        dfs(index + 1, current_result + numbers[index], add - 1, sub, mul, div)
    
    # 뺄셈
    if sub > 0:
        dfs(index + 1, current_result - numbers[index], add, sub - 1, mul, div)
    
    # 곱셈
    if mul > 0:
        dfs(index + 1, current_result * numbers[index], add, sub, mul - 1, div)
    
    # 나눗셈 (C++14 방식)
    if div > 0:
        if current_result < 0:
            dfs(index + 1, -(-current_result // numbers[index]), add, sub, mul, div - 1)
        else:
            dfs(index + 1, current_result // numbers[index], add, sub, mul, div - 1)

# 입력 받기
N = int(input())
numbers = list(map(int, input().split()))
add, sub, mul, div = map(int, input().split())

# 최댓값, 최솟값 초기화
max_result = -sys.maxsize
min_result = sys.maxsize

# DFS 시작
dfs(1, numbers[0], add, sub, mul, div)

# 결과 출력
print(max_result)
print(min_result)

• 내 기존 코드에서는 ,

result = calculate(numbers, perm)    # 기존 코드 

dfs(1, numbers[0], add, sub, mul, div)  # 개선 코드 (백트래킹) 

→ numbers 배열 자체를 넘겼는데 개선 코드에서는 리스트의

가장 첫번째 원소롸 각 연산자들의 갯수를 넘긴다

 

 

• 연산자가 감소하는 식 으로 구현

    # 덧셈
    if add > 0:
        dfs(index + 1, current_result + numbers[index], add - 1, sub, mul, div)
    
    # 뺄셈
    if sub > 0:
        dfs(index + 1, current_result - numbers[index], add, sub - 1, mul, div)
    
    # 곱셈
    if mul > 0:
        dfs(index + 1, current_result * numbers[index], add, sub, mul - 1, div)
    
    # 나눗셈 (C++14 방식)
    if div > 0:
        if current_result < 0:
            dfs(index + 1, -(-current_result // numbers[index]), add, sub, mul, div - 1)
        else:
            dfs(index + 1, current_result // numbers[index], add, sub, mul, div - 1)

 

 

• 기존 500ms ⇒ 48ms 대폭 감소
• ⇒ 백트래킹(DFS) 활용 하면 유리해지는 문제임