[백준 실버1] 연산자 끼워넣기 (#14888, 백트래킹 문제)

 

(문제 링크)

 

📌 1. 문제 설명 요약

• N개의 수가 주어지고, 이 사이에 N-1개의 연산자 (+, -, *, /)를 끼워넣어 계산해야 함.

• 수의 순서는 바뀌지 않고, 연산자 순서를 바꿔서 가능한 모든 경우를 탐색해야 함.

• 연산자 우선순위는 고려하지 않고, 왼쪽에서 오른쪽 순서대로 연산을 진행.

• 가능한 모든 식을 만들고 최댓값과 최솟값을 출력해야 함.

• 나눗셈(÷)은 C++14 기준으로 수행 (음수를 나눌 때 처리 방식이 다름).

 

 

📌 2. 문제를 보자마자 생각하는 풀이 흐름

 

💡 어떻게 접근해야 할까?

• 주어진 숫자는 그대로 사용하고, 연산자들의 순서만 바꿔서 탐색해야 함.

• 가능한 모든 연산 조합을 탐색하려면 완전 탐색(백트래킹)을 사용해야 함.

• N-1개의 연산자가 있기 때문에 연산자 개수가 줄어드는 구조를 활용하면 됨.

 

💡 풀이 아이디어

1. 재귀 함수(backtrack)을 사용하여 모든 연산자 조합을 탐색.

• 현재 결과값을 계산하면서, 남은 연산자를 하나씩 사용하여 백트래킹 수행.

• 모든 숫자를 사용하면 최댓값 & 최솟값을 갱신.

2. 연산자 사용 후 다시 되돌리는(백트래킹) 과정이 필요.

• 연산자를 하나 사용했다면, 연산 후 다시 돌려놓아야 다른 경우도 탐색 가능.

3. 나눗셈(÷) 연산은 C++14 기준을 적용해야 함.

• 음수를 나눌 때는 -(-a // b)로 변환.

 

 

📌 3. 코드 설명

 

1. 초기 입력 및 변수 설정

N = int(sys.stdin.readline().strip())  # 숫자 개수
numbers = list(map(int, sys.stdin.readline().split()))  # 수열
add, sub, mul, div = map(int, sys.stdin.readline().split())  # 연산자 개수

 

2. 백트래킹 함수

def backtrack(index, result):

• index: 현재 연산할 숫자의 위치.
• result: 현재까지 계산된 값.

3. 종료 조건

if index == N:
    max_result = max(max_result, result)
    min_result = min(min_result, result)
    return

• 종료 조건: 모든 숫자 사용 완료
• 모든 연산을 수행 후, 최댓값 & 최솟값 갱신

4. 연산자 사용 후 백트래킹

# 덧셈 연산자 사용
    if add > 0:
        add -= 1  # 연산자 사용
        backtrack(index + 1, result + numbers[index])
        add += 1  # 백트래킹 (연산자 개수 복구)

    # 뺄셈 연산자 사용
    if sub > 0:
        sub -= 1
        backtrack(index + 1, result - numbers[index])
        sub += 1

    # 곱셈 연산자 사용
    if mul > 0:
        mul -= 1
        backtrack(index + 1, result * numbers[index])
        mul += 1

    # 나눗셈 연산자 사용
    if div > 0:
        div -= 1
        # C++14 기준: 음수를 나눌 때 양수로 변환 후 나눈 뒤 다시 음수로 변환
        if result < 0:
            backtrack(index + 1, -(-result // numbers[index]))
        else:
            backtrack(index + 1, result // numbers[index])
        div += 1  # 백트래킹 (연산자 개수 복구)

• 각 연산자 사용 후 다음 숫자로 진행.
• 연산이 끝난 후 백트래킹을 통해 연산자 개수 복구.

 

📌 4. 코드 실행 흐름

 

입력 예제

6
1 2 3 4 5 6
2 1 1 1

 

 

백트래킹 호출 흐름

backtrack(1, 1)
 ├── backtrack(2, 3)   # 1 + 2 = 3
 │   ├── backtrack(3, 6)   # 3 + 3 = 6
 │   ├── backtrack(3, 0)   # 3 - 3 = 0
 │   ├── backtrack(3, 9)   # 3 × 3 = 9
 │   ├── backtrack(3, 1)   # 3 ÷ 3 = 1

 

 

 

📌 5. 전체 코드

import sys

# 입력 받기
N = int(sys.stdin.readline().strip())  # 숫자의 개수
numbers = list(map(int, sys.stdin.readline().split()))  # 수열
add, sub, mul, div = map(int, sys.stdin.readline().split())  # 연산자 개수

# 최댓값, 최솟값 초기화
max_result = -int(1e9)  # -10억
min_result = int(1e9)   # 10억

def backtrack(index, result):
    """백트래킹을 사용해 연산자를 끼워넣으며 최댓값, 최솟값 계산"""
    global add, sub, mul, div, max_result, min_result  # 전역 변수 사용

    # 종료 조건: 모든 숫자를 사용한 경우
    if index == N:
        max_result = max(max_result, result)
        min_result = min(min_result, result)
        return

    # 덧셈 연산자 사용
    if add > 0:
        add -= 1  # 연산자 사용
        backtrack(index + 1, result + numbers[index])
        add += 1  # 백트래킹 (연산자 개수 복구)

    # 뺄셈 연산자 사용
    if sub > 0:
        sub -= 1
        backtrack(index + 1, result - numbers[index])
        sub += 1

    # 곱셈 연산자 사용
    if mul > 0:
        mul -= 1
        backtrack(index + 1, result * numbers[index])
        mul += 1

    # 나눗셈 연산자 사용
    if div > 0:
        div -= 1
        # C++14 기준: 음수를 나눌 때 양수로 변환 후 나눈 뒤 다시 음수로 변환
        if result < 0:
            backtrack(index + 1, -(-result // numbers[index]))
        else:
            backtrack(index + 1, result // numbers[index])
        div += 1  # 백트래킹 (연산자 개수 복구)

# 백트래킹 시작 (첫 번째 숫자를 초기값으로 설정)
backtrack(1, numbers[0])

# 최댓값, 최솟값 출력
print(max_result)
print(min_result)