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

💡문제접근

• 처음엔 모든 수의 사이에 들어갈 수 있는 연산자 순열을 구해서 중복을 제거해 최대한 메모리 사용을 방지한 다음 permutations을 이용해서 최댓값, 최솟값을 구하는 방식으로 코드를 작성했지만 시간초과(TLE)가 발생했다.
• 두 번째로 택한 방법은 백트래킹이었다. 사실 이 방법은 내 머릿속으로 생각해낸 방법이 아니고 질문게시판을 통해 알게 된 방법이었다.

💡코드(메모리 : 30616KB, 시간 : 184ms)

import sys
# 최대 재귀 깊이 설정
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

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

# 최댓값
Max = -1000000000
# 최솟값
Min = 1000000000


def DFS(idx, result):
    global Max, Min
    # idx가 N에 도달 즉, 모든 수들 사이에 연산자가 들어갔다면?
    if idx == N:
        Max = max(Max, result)
        Min = min(Min, result)
        return
	
    # 더하기 연산자가 존재한다면?
    if op_cnt[0] > 0:
    	# 더하기 연산자 1개 사용
        op_cnt[0] -= 1
        # 더하기 연산자를 사용했으므로 idx는 1만큼 증가하고 result에 배열 A의 두 번째 원소를 더해준다.
        DFS(idx + 1, result + A[idx])
        # 원상복구
        op_cnt[0] += 1
    # 빼기 연산자가 존재한다면?
    if op_cnt[1] > 0:
    	# 빼기 연산자 1개 사용
        op_cnt[1] -= 1
		# 빼기 연산자를 사용했으므로 idx는 1만큼 증가하고 result에 배열 A의 두 번째 원소를 빼준다.
        DFS(idx + 1, result - A[idx])
        # 원상복구
        op_cnt[1] += 1
    # 곱하기(위와 동일)
    if op_cnt[2] > 0:
        op_cnt[2] -= 1
        DFS(idx + 1, result * A[idx])
        op_cnt[2] += 1
    # 나누기(위와 동일)    
    if op_cnt[3] > 0:
        op_cnt[3] -= 1
        DFS(idx + 1, int(result / A[idx]))
        op_cnt[3] += 1

# 첫 번째 숫자 idx는 1이고 초기값은 배열 A의 첫 번째 원소
DFS(1, A[0])
print(Max)
print(Min)

💡소요시간 : 30m