[백준 15658] 연산자 끼워넣기(2)

문제

N개의 수가 있고 +, -, x, ÷ 네 개의 연산자가 있다. 

각각의 연산자 개수는 한정적이고 이를 활용하여 N개의 수에 연산을 적용했을 때 최댓값과 최솟값을 구하라.

연산자는 수의 개수보다 많을 수 있다.

단, 연산자 우선순위는 적용하지 않는다.

 

=> 연산자 끼워넣기 (1)은 N개의 수가 있다면 N-1개의 연산자가 있었지만 이 문제는 그 이상의 개수가 있을 수 있다.

 

입력

첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1보다 크거나 같고, 4N보다 작거나 같은 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱셈(×)의 개수, 나눗셈(÷)의 개수이다. 

 

출력

첫째 줄에 만들 수 있는 식의 결과의 최댓값을, 둘째 줄에는 최솟값을 출력한다. 연산자를 어떻게 끼워넣어도 항상 -10억보다 크거나 같고, 10억보다 작거나 같은 결과가 나오는 입력만 주어진다. 또한, 앞에서부터 계산했을 때, 중간에 계산되는 식의 결과도 항상 -10억보다 크거나 같고, 10억보다 작거나 같다.

---

접근

입력받은 연산자의 개수를 모두 탐색하여 최댓값과 최솟값을 찾아야한다.

이를 위해 백트래킹을 활용하였으며, 재귀호출을 할 때 현재 가리키는 숫자의 인덱스 +1을 전달하고 이 숫자가 N-1이 되었을 때 계산을 하여 최댓값 최솟값을 구한다.

 

구현

아래의 코드는 백트래킹을 통해 완전 탐색을 하는 코드다.

현재의 인덱스가 N-1일 때는 N개의 수에 맞는 연산자를 모두 사용했기 때문에 계산을 하여 최댓값과 최솟값을 찾는다.

그렇지 않을 때는 4개의 연산자를 탐색하여 아직 사용할 연산자가 있을 때 사용을 하고 각 연산에 따라 결과를 넘겨준다.

아래의 for문과 재귀호출을 통해 모든 경우의 수를 탐색할 수 있다.

def solve(total, idx):
    global ans_min, ans_max
    if idx == (N-1):
        ans_min = min(ans_min, total)
        ans_max = max(ans_max, total)
        return

    for i in range(4):
       if oper_list[i] != 0:
           oper_list[i] -= 1
           if i == 0:
               solve(total+numbers[idx+1], idx+1)
           elif i == 1:
               solve(total-numbers[idx+1], idx+1)
           elif i == 2:
               solve(total*numbers[idx+1], idx+1)
           else:
               solve(int(total/numbers[idx+1]), idx+1)

           oper_list[i] += 1

---

전체 코드

import sys
input = sys.stdin.readline

def solve(total, idx):
    global ans_min, ans_max
    if idx == (N-1):
        ans_min = min(ans_min, total)
        ans_max = max(ans_max, total)
        return

    for i in range(4):
       if oper_list[i] != 0:
           oper_list[i] -= 1
           if i == 0:
               solve(total+numbers[idx+1], idx+1)
           elif i == 1:
               solve(total-numbers[idx+1], idx+1)
           elif i == 2:
               solve(total*numbers[idx+1], idx+1)
           else:
               solve(int(total/numbers[idx+1]), idx+1)

           oper_list[i] += 1

N = int(input())
numbers = list(map(int, input().split()))
# + - x /
oper_list = list(map(int, input().split()))
ans_max = -1000000001
ans_min = 1000000001

solve(numbers[0], 0)
print(ans_max)
print(ans_min)