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

김바덕·2023년 6월 22일

백준 백트래킹 파이썬

백준

목록 보기

14/23

💻 문제

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

💻 문제 풀이

이 문제는 주어진 수열에 주어진 연산자를 적절히 삽입하여 만들 수 있는 최댓값과 최솟값을 구하는 문제

✅ 문제를 해결하기 위해 백트래킹(Backtracking) 알고리즘을 사용하면 쉽게 해결할 수 있다.

주어진 수열의 숫자와 연산자를 모두 활용하여 가능한 모든 계산식을 생성하고, 계산식의 결과를 최댓값과 최솟값과 비교하여 갱신하는 방식으로 문제를 해결할 수 있다.

백트래킹 알고리즘을 구현할 때, 재귀 함수를 사용하여 문제를 해결하는 방식이 일반적이다.
재귀 함수는 모든 경우의 수를 탐색하면서 중간 결과를 저장하고, 최종 결과를 도출하는 데 활용된다.
이때, 백트래킹 알고리즘은 가지치기(Pruning)를 통해 불필요한 경우의 수를 미리 제거하여 실행 시간을 단축시킬 수 있음

💻 백트래킹 알고리즘(Backtracking)

백트래킹은 재귀적으로 문제를 하나씩 풀어가면서 현재 재귀를 통해 확인 중인 노드(상태)가 제한된 조건에 위배되는지 판단하고,

만약 해당 노드가 제한된 조건을 위배한다면 그 노드를 제외하고 다음 단계로 나아가는 방식

가장 중요한 점은 제한조건을 위배한다면 그 노드를 제외한다는 점 이다.

가지치기

백트래킹은 현재 상태에서 다음상태로 가는 모든 경우의 수를 찾아서 이 모든 경우의수가 더 이상 유망하지 않다고 판단되면 이전의 상태로 돌아가는 것을 말한다.
여기서 더 이상 탐색할 필요가 없는 상태를 제외하는 것을 가지치기(pruning)라고도 한다.
따라서 한마디로 정의하면 DFS를 통해 모든 노드를 깊이 우선 탐색을 하면서 더 이상 필요가 없는 부분을 쳐내는 행위를 백트래킹(가지치기) 이라고 생각하면된다.

💻 소스 코드

# 숫자의 개수
n = int(input())

# 주어진 수열
numbers = list(map(int, input().split()))

# 덧셈, 뺄셈, 곱셈, 나눗셈 연산자의 개수
add, subtract, multiply, divide = map(int, input().split())

# 최댓값과 최솟값 초기화
max_value = float('-inf')
min_value = float('inf')

# 백트래킹 알고리즘을 이용하여 모든 경우의 수 탐색
def backtrack(idx, result, add, subtract, multiply, divide):
    global max_value, min_value

    # 모든 숫자를 사용한 경우 최댓값과 최솟값 갱신
    if idx == n:
        max_value = max(max_value, result)
        min_value = min(min_value, result)
        return

    # 덧셈 연산자 사용
    if add > 0:
        backtrack(idx + 1, result + numbers[idx], add - 1, subtract, multiply, divide)
    # 뺄셈 연산자 사용
    if subtract > 0:
        backtrack(idx + 1, result - numbers[idx], add, subtract - 1, multiply, divide)
    # 곱셈 연산자 사용
    if multiply > 0:
        backtrack(idx + 1, result * numbers[idx], add, subtract, multiply - 1, divide)
    # 나눗셈 연산자 사용
    if divide > 0:
        # 나눗셈 연산은 음수를 양수로 나눌 때와 같은 효과를 가지지 않으므로 주의해야 합니다.
        if result < 0:
            backtrack(idx + 1, -(-result // numbers[idx]), add, subtract, multiply, divide - 1)
        else:
            backtrack(idx + 1, result // numbers[idx], add, subtract, multiply, divide - 1)

# 백트래킹 알고리즘 호출
backtrack(1, numbers[0], add, subtract, multiply, divide)

# 결과 출력
print(max_value)
print(min_value)