[백준] 14888번: 연산자 끼워넣기 (파이썬)

✅문제: 14888번

📌개념정리

(1) 재귀 호출

• 정의: 함수가 자기 자신을 호출하는 프로그래밍 기법
• 문제를 작은 부분으로 나누어 반복적으로 해결할 수 있음.
• 이 문제에서는 모든 연산자의 가능한 조합을 확인하기 위해 재귀 호출을 통해 각 연산자를 하나씩 적용하여 결과를 탐색함.

(2) 백트래킹

• 정의: 해를 찾는 도중에 막히면 이전 단계로 돌아가 다른 경로를 시도하는 기법
• 가능한 모든 경우의 수를 탐색할 때 자주 사용됨.
• 연산자를 사용할 때마다 해당 연산자를 감소시키고, 재귀 호출이 끝나면 다시 원래 개수로 복구하여 다른 경로를 탐색함.

📌문제풀이

주어진 숫자와 연산자(+ - * /)를 사용해 가능한 모든 결과를 계산한 뒤, 그중 최대값과 최소값을 구하는 문제임.

• 제약사항
  1. 각 연산자는 주어진 개수만큼 사용할 수 있음.
  2. 나눗셈 연산은 정수 나눗셈으로 처리하며, 음수를 나눌 때는 C++의 기준을 따라 몫이 음수일 경우, 양수로 변환 후 나눗셈 연산을 수행한 뒤 다시 음수로 변환해야 함.

각 숫자와 연산자 조합을 탐색하며 최종 최대, 최소값을 찾아야 하는데, 이를 위해 재귀 함수와 백트래킹을 활용하여 모든 경우의 수를 탐색함.

1. 모든 입력을 받아와서 data 변수에 저장하고, 이를 통해 숫자와 연산자 개수를 추출함.
2. 재귀 함수 calculate를 통해 가능한 모든 연산자 조합을 시도하면서 결과를 탐색함.
3. 각 연산자에 대해 남은 개수를 확인하여, 사용할 수 있는 연산자를 재귀적으로 시도함.
4. 음수를 나눌 때는 절댓값으로 나눈 뒤 결과를 음수로 변환함.
5. 모든 가능한 연산 결과를 탐색한 후, 최대값과 최소값을 갱신하여 반환함.

import sys
input = sys.stdin.read

def calculate(numbers, operators, current_result, index, max_result, min_result):
    if index == len(numbers):
        return max(max_result, current_result), min(min_result, current_result)
    
    next_number = numbers[index]
    results = []

    if operators[0] > 0:
        operators[0] -= 1
        results.append(calculate(numbers, operators, current_result + next_number, index + 1, max_result, min_result))
        operators[0] += 1
    if operators[1] > 0:
        operators[1] -= 1
        results.append(calculate(numbers, operators, current_result - next_number, index + 1, max_result, min_result))
        operators[1] += 1
    if operators[2] > 0:
        operators[2] -= 1
        results.append(calculate(numbers, operators, current_result * next_number, index + 1, max_result, min_result))
        operators[2] += 1
    if operators[3] > 0:
        operators[3] -= 1
        if current_result < 0 and next_number > 0:
            results.append(calculate(numbers, operators, -(abs(current_result) // next_number), index + 1, max_result, min_result))
        else:
            results.append(calculate(numbers, operators, current_result // next_number, index + 1, max_result, min_result))
        operators[3] += 1
    
    for result in results:
        max_result = max(max_result, result[0])
        min_result = min(min_result, result[1])
    
    return max_result, min_result

data = input().split()
n = int(data[0])
numbers = list(map(int, data[1:n+1]))
operators = list(map(int, data[n+1:n+5]))

initial_result = numbers[0]
max_result, min_result = calculate(numbers, operators, initial_result, 1, float('-inf'), float('inf'))

print(max_result)
print(min_result)

📌후기

• 음수 나눗셈 처리에서 절댓값을 이용하는 과정에서 어떻게 할지 고민이 들었음.
• 재귀와 백트래킹을 통해 모든 경우의 수를 탐색하는 방법에 대해서 알 수 있었던 문제임.
• 언어별로 연산 방식 차이점에 대해 알 수 있었음.