[백준] 삼성 SW 역량 테스트 기출 문제 14888번 : 연산자 끼워넣기 (파이썬/Python)

[백준] 삼성 SW 역량 테스트 기출 문제 14888번 : 연산자 끼워넣기 (파이썬/Python)

정답 전체 코드

import sys

#연산하는 함수
def calculate(op, a, b):
    if op == '+':
        return a + b
    elif op == '-':
        return a - b
    elif op == '*':
        return a * b
    elif op == '/':
        # 음수 나눗셈 처리
        if a * b < 0 and a % b != 0:
            return a // b + 1
        return a // b

# 백트래킹
def backtrack(index, current_result):
    global addition_count, subtraction_count, multiplication_count, division_count

    if index == n:
        results.add(current_result)
        return
    
    if addition_count > 0:
        addition_count -= 1
        backtrack(index + 1, calculate('+', current_result, input_arr[index]))
        addition_count += 1
    
    if subtraction_count > 0:
        subtraction_count -= 1
        backtrack(index + 1, calculate('-', current_result, input_arr[index]))
        subtraction_count += 1
    
    if multiplication_count > 0:
        multiplication_count -= 1
        backtrack(index + 1, calculate('*', current_result, input_arr[index]))
        multiplication_count += 1
    
    if division_count > 0:
        division_count -= 1
        backtrack(index + 1, calculate('/', current_result, input_arr[index]))
        division_count += 1    
    
input = sys.stdin.readline

n = int(input())
input_arr = list(map(int, input().strip().split()))

addition_count, subtraction_count, multiplication_count, division_count = map(int, input().strip().split())

results = set()

backtrack(1, input_arr[0])
print(max(results))
print(min(results))

문제 설명

위 문제는 N개의 수와 이 수들 사이에 끼워넣을 수 있는 N-1개의 연산자가 주어졌을때, 만들 수 있는 식의 결과가 최대인 것과 최소인 것을 구하는 문제이다. 사용할 수 있는 연산자는 덧셈, 뺄셈, 곱셉, 나눗셈의 네 가지이다. 문제의 핵심은 바로 주어진 수의 순서를 바꾸지 않으면서, 모든 가능한 연산자 조합을 시도하여 식의 결과값을 최대화하거나 최소화하는 것이다.

알고리즘 설명

위 문제를 해결하기 위해서 백트래킹 알고리즘을 사용한다. 백트래킹은 해를 찾아가는 도중에 해가 아니면 되돌아가서 다시 해를 찾아가는 기법이다. 이 문제에서는 각 단계에서 사용할 수 있는 연산자가 무엇인지에 따라 다음 단계로 진행하거나 되돌아간다.

1. 입력으로 주어진 수의 개수 N, 각 수를 담는 배열 input_arr, 그리고 각 연산자의 개수를 나타내는 네 개의 변수를 입력받을 준비를 한다.

2. 연산 함수는 두 수와 연산자를 입력으로 받아서 결과를 반환하는 calculate 함수를 정의한다. 이 함수는 네 가지 연산자에 대해 적절히 연산을 수행하며 특히 나누셈 연산 시 음수 나눗셈 처리에 적용한다.

3. 백트래킹 함수 실행한다. 처음에는 배열의 첫 번째 수를 시작 결과값으로 하고, backtrack 함수를 호출하여 모든 가능한 식을 탐색한다. 이 함수는 현재까지의 계산 결과와 처리할 다음 수의 인덱스(순서)를 매개변수로 받는다.

4. 가능한 모든 연산자에 대해 현재 수와 다음 수를 연산하고, 연산자 개수를 하나 줄인 후 다시 backtrack 함수를 호출한다. 모든 수를 처리한 후(즉, 인덱스가 N에 도달했을 떄) 현재까지의 계산 결과를 결과 set 에 추가한다.

5. 탐색이 끝나면 결과 집합에서 최댓값과 최소값을 찾아 출력한다.

코드 설명

• 입력을 받고 필요한 변수를 초기화한다. results 집합은 가능한 모든 결과를 저장한다.
• calculate 함수는 주어진 연산자에 따라 두 수의 연산 결과를 반환한다. 나눗셈 시 음수 처리를 위해 특별한 조건을 적용하기 위함이다.
• backtrack 함수는 현재 인덱스와 현재까지의 계산 결과를 인자로 받아, 가능한 모든 연산자를 적용하며 재귀적으로 다음 단계로 진행한다. 각 연산자를 사용할 때마다 해당 연산자의 개수를 줄이고, 재귀 호출이 끝난 후에는 다시 개수를 복원한다.
• 모든 수를 고려했을 때(즉, index == n일 때) 현재의 계산 결과를 results 집합에 추가한다.
• 최종적으로 results 집합에서 최대값과 최소값을 찾아 출력한다.

결론

이 문제를 해결하기 위해서 백트래킹 기법을 통해서 모든 가능한 연산자 조합을 시도하면서, 각 경우에 대해 계산된 결과를 추적하고, 그중 최댓값과 최솟값을 찾는 방식으로 해결할 수 있었다. 이러한 접근 방식은 가능한 모든 경우의 수를 고려하기 때문에, 문제의 조건 내에서 가장 좋은 결과를 도출할 수 있다.