백준 연산자 끼워넣기 [14888] 파이썬(Python) 코드 + 해설

백준 14888 연산자 끼워넣기 문제

해결 전략

이 문제는 가능한 모든 연산자 배치를 시도하여 결과의 최댓값과 최솟값을 찾는 백트래킹(DFS) 문제입니다.

알고리즘 개요

1. 입력받기: 수열과 연산자 개수를 입력받습니다.
2. 백트래킹 함수 구현:
   • 현재까지의 계산 결과, 사용한 연산자 개수, 수열의 인덱스를 인자로 받습니다.
   • 모든 연산자 배치를 시도합니다.
   • 각 연산자 배치마다 결과를 계산하고, 최댓값과 최솟값을 갱신합니다.
3. 나눗셈 구현:
   • 나눗셈에서 음수 처리를 문제의 요구사항에 맞게 구현합니다.
4. 결과 출력: 최종적으로 구한 최댓값과 최솟값을 출력합니다.

 

핵심 포인트

• 백트래킹을 통한 완전 탐색: 모든 가능한 연산자 배치를 시도하여 최적해를 찾습니다.
• 나눗셈의 정확한 구현: 파이썬의 나눗셈 연산과 문제의 요구사항의 차이를 이해하고 올바르게 구현합니다.
• 연산자 우선순위 무시: 계산은 입력된 수의 순서대로, 연산자 우선순위를 무시하고 앞에서부터 진행합니다.
• 음수 나눗셈 처리: 음수를 양수로 나눌 때는 절댓값으로 나눈 몫을 음수로 변환합니다.

 

정답 파이썬 코드

N = int(input())
A = list(map(int, input().split()))
operators = list(map(int, input().split()))  # [+, -, *, /]

max_result = -1e9
min_result = 1e9

def calculate(a, b, operator_index):
    if operator_index == 0:  # 덧셈
        return a + b
    elif operator_index == 1:  # 뺄셈
        return a - b
    elif operator_index == 2:  # 곱셈
        return a * b
    elif operator_index == 3:  # 나눗셈
        return divide(a, b)

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

def dfs(index, current_result):
    global max_result, min_result
    if index == N:
        max_result = max(max_result, current_result)
        min_result = min(min_result, current_result)
        return
    for i in range(4):
        if operators[i] > 0:
            operators[i] -= 1  # 연산자 사용
            next_result = calculate(current_result, A[index], i)
            dfs(index + 1, next_result)
            operators[i] += 1  # 연산자 복구 (백트래킹)

dfs(1, A[0])

print(max_result)
print(min_result)

설명

• 백트래킹(DFS)을 사용하여 가능한 모든 연산자 배치를 시도합니다.
• 각 단계마다 남은 연산자를 확인하고, 재귀적으로 다음 수와 연산을 수행합니다.
• 나눗셈 연산에서 음수 처리를 정확히 구현하여 문제의 요구사항에 맞게 합니다.
• 최댓값과 최솟값을 전역 변수로 관리하며, 모든 경우의 수를 탐색한 후 결과를 출력합니다.

14888 연산자 끼워넣기 정답

 

도움이 되셨다면 공감과 댓글 부탁드립니다.