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

방법이있지·2025년 6월 4일

문제풀이 크래프톤 정글

[정글] 특히 어려웠던 녀석들

목록 보기

25/35

백준 / 실버 1 / 14888. 연산자 끼워넣기

생각해봅시다!!

배열 $A$ 내 $N$ 개의 수에, $N - 1$ 개의 연산자를 끼워넣은 뒤, 최대값 및 최소값을 구하는 문제입니다.
일단 모든 연산자 조합의 경우을 따져봐서 연산의 결과를 확인하고, 최대값 및 최소값을 구해야 합니다.
제일 직관적인 방법은, 재귀를 이용해 풀이하는 겁니다.

e.g., A = [1, 2, 3, 4]이며, $+$ 1개, $-$ 1개, $\times$ 1개가 주어졌을 때

현재 계산된 값을 노드, 다음 연산을 간선으로 둔 트리에서 DFS를 한다고 생각하면 됩니다.

풀이

N = int(input())
arr = list(map(int, input().split()))
pl, mi, mu, di = map(int, input().split())

max_value = -float('inf')	# 음의 무한
min_value = float('inf')	# 양의 무한
result = 0

def calculate(i, result, pl, mi, mu, di):
    # 전역 변수에 값을 새로 대입하려면 필요
    global max_value, min_value
    
    # 모든 연산이 완료됐을 때 값 갱신
    if i == N:
        min_value = min(min_value, result)
        max_value = max(max_value, result)
    
    # 연산자가 남아 있을 때만 재귀 호출
    if pl > 0:
        calculate(i + 1, result + arr[i], pl - 1, mi, mu, di)
    if mi > 0:
        calculate(i + 1, result - arr[i], pl, mi - 1, mu, di)
    if mu > 0:
        calculate(i + 1, result * arr[i], pl, mi, mu - 1, di)
    if di > 0:
        if result < 0:
        	# 음수를 양수로 나누는 게 특이한데, 문제에 잘 설명되어 있음
            next = -((-result) // arr[i])
        else:
            next = result // arr[i]
        calculate(i + 1, next, pl, mi, mu, di - 1)
        
calculate(1, arr[0], pl, mi, mu, di)
print(max_value)
print(min_value)

최대값, 최소값 집계

정답으로 출력해야 하는 최대값 및 최소값은 max_value, min_value 변수로 지정합니다.
- 재귀함수 내에서 global 선언을 통해, 값을 수정할 수 있게 합니다.
- 함수 내에서 전역 변수를 사용하는 것은 global 없이 가능하지만, 다른 값을 새로 대입하려면 global을 사용해야 합니다.

재귀함수 정의

현재까지 구한 값 result에 숫자들이 담긴 값 arr의 i번째 값을 연산하는 calculate 함수를 정의합니다.
- 초기값은 result는 arr[0], i는 1로 둡니다.
- 매개변수 pl, mi, mu, di로 각각 남은 덧셈, 뺄셈, 곱셈, 나눗셈 연산자 수를 보냅니다.
- 호출할 때마다 result 매개변수 자리에 연산 결과를 대입하는 식으로 구현합니다.
이 문제에선 음수를 양수를 나눌 때 특이하게 나누는데... 문제에 잘 설명되어 있습니다.
--((-A) // B)와 같이 음수 값 A를 부호반전하고, B로 나눈 뒤 다시 부호반전하면 됩니다.

분기 설정

조건문으로 덧셈 / 뺄셈 / 곱셈 / 나눗셈을 하는 경우를 분기합니다.
- 단, 해당 연산의 개수가 남아 있을 때만 이후 코드 실행할 수 있습니다.
- 다음 숫자를 연산하기 위해, i+1번째 숫자에 대해 calculate를 재귀 호출합니다.
- 연산을 완료한 값을 result 매개변수로 보내고, 해당 연산에 해당하는 매개변수를 1 감소시켜 calculate를 호출하면 됩니다.

종료조건