[백준][20단계 백트래킹] 14888번 /연산자 끼워넣기 (파이썬/Python)

1. 문제 설명

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

2. 코드

import sys
input = sys.stdin.readline

N = int(input().strip())
nums = list(map(int,input().split()))
plus,minus,mul,div = map(int,input().split())

max_value = -10**9 - 1
min_value = 10**9 + 1

def my_div(a,b):
    if a >= 0:
        return a//b
    else:
        return -(-a//b)

def dfs(idx, value, p, m, mu, d):
    global max_value, min_value
    
    if idx == N:
        max_value = max(max_value, value)
        min_value = min(min_value, value)
        return
    next_num = nums[idx]
    if p > 0:
        dfs(idx + 1, value + next_num, p - 1, m, mu, d)
    if m > 0:
        dfs(idx + 1, value - next_num, p, m -1, mu, d)
    if mu > 0:
        dfs(idx + 1, value * next_num, p, m, mu - 1, d)
    if d > 0:
        dfs(idx + 1, my_div(value, next_num), p, m, mu, d - 1)
dfs(1, nums[0], plus, minus, mul, div)

print(max_value)
print(min_value)

3. 풀이 과정

최댓값은 10억, 최댓값은 -10억으로 한다.

나눗셈은 C++ 기준이므로 지정해준다.

idx가 N이면 최댓값과 최솟값을 비교해서 저장한다.

다음 값은 nums[idx]로 지정한다.

더하기는 p, 빼기는 m, 곱하기는 mu, 나누기는 d로 지정한다.

p부터 값이 있으면 재귀를 진행한다.

재귀가 끝나면 max_value,min_value를 출력한다.

4. 자투리 개념

• 백트래킹 알고리즘
  - 정답을 구성해 가는 중간 단계들을 체계적으로 탐색하되, 불필요한 가지는 일찍 잘라내는(Pruning) 깊이우선탐색(DFS)

핵심 아이디어

• 문제의 해 공간(Search Space):
  가능한 모든 해(또는 부분해)를 트리 형태로 생각합니다. 루트는 “아무 것도 선택하지 않음”, 깊이 d는 “d개 선택 완료”.
• 부분해(Partial Solution):
  아직 완성은 아니지만 제약을 만족하며 확장될 수 있는 중간 상태.
• DFS + 되돌리기(Backtrack):
  하나를 선택(choose) → 더 내려가서 탐색(explore) → 돌아오며 선택을 취소(unchoose)합니다.
• 가지치기(Pruning):
  제약을 위반하거나, 더 진행해도 정답이 절대 나오지 않을 “가지”는 즉시 탐색을 멈춥니다.

공통 템플릿

def backtrack(state):
    if 완성조건(state):
        정답 처리
        return

    for candidate in 후보집합(state):  # 보통 정렬/오름차순으로 순회
        if 제약을 만족(candidate, state):  # 가지치기 1차
            state에 candidate를 반영(choose)
            backtrack(state)
            state에서 candidate를 되돌리기(unchoose)  # 핵심