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

💡문제접근

• 연산 기호의 개수에 맞춰서 최댓값과 최솟값을 구하는 백트래킹 문제였다. 앞서 풀었던 N과 M 시리즈 문제를 다시 풀어보면서 이해하니까 문제가 쉽게 풀렸다.

💡코드(메모리 : 31256KB, 시간 : 68ms)

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

N = int(input().strip())
A_li = list(map(int, input().strip().split()))
op_cnt = list(map(int, input().strip().split()))

Max = -1000000000
Min = 1000000000

def recursion(idx, res):
    global Max, Min
    if idx == N:
        Max = max(Max, res)
        Min = min(Min, res)
        return
    # 덧셈의 개수
    if op_cnt[0] > 0:
        op_cnt[0] -= 1
        recursion(idx + 1, res + A_li[idx])
        op_cnt[0] += 1
    # 뺄셈의 개수
    if op_cnt[1] > 0:
        op_cnt[1] -= 1
        recursion(idx + 1, res - A_li[idx])
        op_cnt[1] += 1
    # 곱셈의 개수
    if op_cnt[2] > 0:
        op_cnt[2] -= 1
        recursion(idx + 1, res * A_li[idx])
        op_cnt[2] += 1
    # 나눗셈의 개수
    if op_cnt[3] > 0:
        op_cnt[3] -= 1
        recursion(idx + 1, int(res / A_li[idx]))
        op_cnt[3] += 1

recursion(1, A_li[0])
print(Max)
print(Min)

💡소요시간 : 10m