💡문제접근
- 처음엔 모든 수의 사이에 들어갈 수 있는 연산자 순열을 구해서 중복을 제거해 최대한 메모리 사용을 방지한 다음
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
if idx == N:
Max = max(Max, result)
Min = min(Min, result)
return
if op_cnt[0] > 0:
op_cnt[0] -= 1
DFS(idx + 1, result + A[idx])
op_cnt[0] += 1
if op_cnt[1] > 0:
op_cnt[1] -= 1
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
DFS(1, A[0])
print(Max)
print(Min)
💡소요시간 : 30m