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

문제
N개의 수로 이루어진 수열이 있다. 수와 수 사이에 N-1개의 연산자를 끼워넣어 최댓값과 최솟값을 구하라
사용할 수 있는 연산자의 수는 주어진다.

입력
첫째 줄에 수의 개수 N(2이상 11이하)이 주어진다.
둘째 줄에 N개의 수가 주어지며
셋째 줄에 + - x / 순으로 개수가 주어진다.

출력
첫째 줄에 최댓값
둘째 줄에 최솟값

---

접근

수열에서 앞의 숫자를 시작으로 그 다음 수와 연산을 진행한다.

연산자는 사용할 수 있는 개수가 정해져있기 때문에 연산자의 수가 담긴 리스트를 탐색하여 연산자가 남아있다면 그에 해당하는 연산을하도록 한다.

 

구현

필요한 정보를 입력받으며 최댓값과 최솟값 비교를 위한 수를 설정한다. 중간 결과를 포함한 모든 결과가 -10억 이상 10억 이하이기 때문에 아래와 같이 설정해주었다.

N = int(input())
numbers = list(map(int, input().split()))
# + - * / 순
oper = list(map(int, input().split()))
ans_max = -1000000001
ans_min = 1000000001

 

이후에 solve()에서 최댓값과 최솟값을 구한다.

먼저 지금까지의 합과 다음 수를 가리킬 인덱스, 연산자의 정보가 담긴 리스트를 넘겨준다.

for문을 통해 어떤 연산자가 남아있는지 탐색을 하여 연산자가 발견되면 total과 idx가 가리키는 수에 해당 연산을 진행하여 넘겨준다.

이때 연산자를 사용했으면 해당 연산자를 -1하고 다시 돌아왔을 때 +1해준다.

 

나눗셈의 경우 음수를 나눌 때 양수로 바꿔 몫을 취한 뒤에 다시 음수로 바꿔준다고 하였다. 이를 위해 python에서 "/"를 사용하여 나누기하고 int형으로 변경하였다.

def solve(total, idx, oper):
    global ans_max, ans_min
    if sum(oper) == 0:
        ans_max = max(ans_max, total)
        ans_min = min(ans_min, total)
        return

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

---

전체 코드

import sys
input = sys.stdin.readline

def solve(total, idx, oper):
    global ans_max, ans_min
    if sum(oper) == 0:
        ans_max = max(ans_max, total)
        ans_min = min(ans_min, total)
        return

    for i in range(4):
        if oper[i]:
            if i == 0:
                oper[i] -= 1
                solve(total+numbers[idx], idx+1, oper)
                oper[i] += 1
            elif i == 1:
                oper[i] -= 1
                solve(total-numbers[idx], idx+1, oper)
                oper[i] += 1
            elif i == 2:
                oper[i] -= 1
                solve(total*numbers[idx], idx+1, oper)
                oper[i] += 1
            elif i == 3:
                oper[i] -= 1
                solve(int(total/numbers[idx]), idx+1, oper)
                oper[i] += 1
N = int(input())
numbers = list(map(int, input().split()))
# + - * / 순
oper = list(map(int, input().split()))
ans_max = -1000000001
ans_min = 1000000001
solve(numbers[0], 1, oper)
print(ans_max)
print(ans_min)