[백준/Python] 14888 연산자 끼워넣기

[백준/Python] 14888 연산자 끼워넣기

정답 코드 및 설명

전체 코드

import sys

#연산하는 함수
def calculate(op, a, b):
    if op == '+':
        return a + b
    elif op == '-':
        return a - b
    elif op == '*':
        return a * b
    elif op == '/':
        # 음수 나눗셈 처리
        if a * b < 0 and a % b != 0:
            return a // b + 1
        return a // b

# 백트래킹
def backtrack(index, current_result):
    global addition_count, subtraction_count, multiplication_count, division_count

    if index == n:
        results.add(current_result)
        return
    
    if addition_count > 0:
        addition_count -= 1
        backtrack(index + 1, calculate('+', current_result, input_arr[index]))
        addition_count += 1
    
    if subtraction_count > 0:
        subtraction_count -= 1
        backtrack(index + 1, calculate('-', current_result, input_arr[index]))
        subtraction_count += 1
    
    if multiplication_count > 0:
        multiplication_count -= 1
        backtrack(index + 1, calculate('*', current_result, input_arr[index]))
        multiplication_count += 1
    
    if division_count > 0:
        division_count -= 1
        backtrack(index + 1, calculate('/', current_result, input_arr[index]))
        division_count += 1    
    
input = sys.stdin.readline

n = int(input())
input_arr = list(map(int, input().strip().split()))

addition_count, subtraction_count, multiplication_count, division_count = map(int, input().strip().split())

results = set()

backtrack(1, input_arr[0])
print(max(results))
print(min(results))

코드 설명

1. 입력 받기

import sys

input = sys.stdin.readline

n = int(input())
input_arr = list(map(int, input().strip().split()))

addition_count, subtraction_count, multiplication_count, division_count = map(int, input().strip().split())

results = set()

n (수열의 길이), input_arr (수열), 그리고 각 연산자(addition_count, subtraction_count, multiplication_count, division_count)의 개수를 입력받는다.
results 에 정답 후보를 전부 저장할 것이다.

2. 백트래킹 함수(backtrack) 호출

# 백트래킹
def backtrack(index, current_result):
    global addition_count, subtraction_count, multiplication_count, division_count

    if index == n:
        results.add(current_result)
        return
    
    if addition_count > 0:
        addition_count -= 1
        backtrack(index + 1, calculate('+', current_result, input_arr[index]))
        addition_count += 1
    
    if subtraction_count > 0:
        subtraction_count -= 1
        backtrack(index + 1, calculate('-', current_result, input_arr[index]))
        subtraction_count += 1
    
    if multiplication_count > 0:
        multiplication_count -= 1
        backtrack(index + 1, calculate('*', current_result, input_arr[index]))
        multiplication_count += 1
    
    if division_count > 0:
        division_count -= 1
        backtrack(index + 1, calculate('/', current_result, input_arr[index]))
        division_count += 1    
        
.......

backtrack(1, input_arr[0]) # 백트래킹 호출

먼저 연산자 수를 저장한 변수의 스코프를 global 로 변경한다. index 는 현재 리스트 접근 값을 뜻한다. 실제로 0번째 원소부터 시작하지만, 1 부터 시작한다. 그 후 연산자 수가 0보다 크면 연산자 수 -1 해주고 백트래킹 기법을 사용하기 위한 재귀 함수를 호출한다. 호출 후 다시 + 1 하는 이유는 모든 원소를 한 번 쓰고 나서 다시 다른 값을 계산해야하는 데 이를 위하여 원상 복귀하는 것이다.

3. 결과 계산 및 출력

print(max(results))
print(min(results))

results 집합에 저장된 모든 결과값들 중 최댓값과 최솟값을 출력하면 된다.