[PYTHON/파이썬] 백준 BAEKJOON 14888번 연산자 끼워넣기

문제링크

https://www.acmicpc.net/problem/14888

문제 풀이

이 문제는 주어진 숫자와 연산자를 사용하여 가능한 모든 식을 만들고, 그 결과 중에서 가장 큰 값과 가장 작은 값을 찾는 문제입니다. 예를 들어, 숫자가 1, 2, 3이고, 연산자가 +, -, *, /일 때, 이 숫자들 사이에 연산자를 넣어서 여러 가지 경우를 계산하는 것입니다.

코드 설명

1. 입력 받기:
   • 숫자의 개수, 숫자 리스트, 각 연산자의 개수를 입력받습니다.
2. 최대값과 최소값 초기화:
   • 최대값은 아주 작은 수로, 최소값은 아주 큰 수로 초기화합니다. 나중에 계산하면서 이 값들을 업데이트할 것입니다.
3. DFS 함수:
   • dfs라는 함수를 정의합니다. 이 함수는 현재 숫자 위치와 지금까지 계산된 값을 인자로 받습니다.
   • 만약 모든 숫자를 다 사용했다면, 현재 계산한 값을 최대값과 최소값과 비교하여 업데이트합니다.
4. 연산자 사용:
   • 덧셈, 뺄셈, 곱셈, 나눗셈을 각각 시도합니다. 사용할 수 있는 연산자가 남아 있다면 그 연산을 수행하고, 다음 숫자로 넘어가기 위해 dfs를 호출합니다.
   • 연산이 끝난 후에는 원래대로 돌아가야 하므로, 연산자 개수를 다시 늘려줍니다.
5. 나눗셈 처리:
   • 나눗셈은 주의해야 합니다. 음수일 때 어떻게 나눌지를 따로 처리합니다. 이 부분은 다른 언어와의 차이점이니 신경 써야 합니다.
6. 결과 출력:
   • 모든 조합을 다 계산한 후, 최댓값과 최솟값을 출력합니다.

 

코드

import sys

input = sys.stdin.readline

# 입력 받기
N = int(input())
lst = list(map(int, input().split()))
operators = list(map(int, input().split()))

# 최댓값과 최솟값 초기화
max_result = -1e9
min_result = 1e9

def dfs(n, current_value):
    global max_result, min_result
    
    # 종료 조건: 모든 수를 사용한 경우
    if n == N - 1:
        max_result = max(max_result, current_value)
        min_result = min(min_result, current_value)
        return
    
    # 각 연산자를 사용하여 재귀 호출
    if operators[0] > 0:  # 덧셈
        operators[0] -= 1
        dfs(n + 1, current_value + lst[n + 1])
        operators[0] += 1
    
    if operators[1] > 0:  # 뺄셈
        operators[1] -= 1
        dfs(n + 1, current_value - lst[n + 1])
        operators[1] += 1
    
    if operators[2] > 0:  # 곱셈
        operators[2] -= 1
        dfs(n + 1, current_value * lst[n + 1])
        operators[2] += 1
    
    if operators[3] > 0:  # 나눗셈
        operators[3] -= 1
        if current_value < 0:  # 음수 나눗셈 처리
            new_value = -(-current_value // lst[n + 1])
        else:
            new_value = current_value // lst[n + 1]
        dfs(n + 1, new_value)
        operators[3] += 1

# DFS 호출
dfs(0, lst[0])

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