728x90
#14888 연산자 끼워넣기
import sys
from itertools import permutations
input = sys.stdin.readline
N = int(input()) #숫자 개수
num = list(map(int, input().split())) #숫자 리스트
oper_num = list(map(int, input().split())) #각 연산자 수가 담긴 리스트
oper_list = ['+', '-', '*', '/'] #연산자 리스트
oper = []
for i in range(len(oper_num)):
for _ in range(oper_num[i]):
oper.append(oper_list[i])
max = -1000000000 #max값이 업데이트 되는것에 방해가 되지 않도록 최소값으로 초기화
min = 1000000000 #min값이 업데이트 되는것에 방해가 되지 않도록 최대값으로 초기화
#연산하는 함수 정의
def calculation():
global max, min
#case문을 이용하여 조건에 따라 앞에서부터 연산진행
for case in permutations(oper, N - 1):
ans = num[0]
for r in range(1, N):
if case[r-1] == '+':
ans += num[r]
elif case[r-1] == '-':
ans -= num[r]
elif case[r-1] == '*':
ans *= num[r]
elif case[r-1] == '/':
ans = int(ans/num[r])
if ans > max:
max = ans
if ans < min:
min = ans
print(max)
print(min)
calculation()
permutation을 이용하여 간단하게 코딩할 수 있지만 시간 복잡도면에서 굉장히 불리하다. 따라서 pypy3을 선택하여 제출했을때만 시간초과가 발생하지 않았다. 따라서 DFS를 이용하여 시간복잡도 문제를 해결한 코드를 찾아보았다.
# 백트래킹 (Python3 통과, PyPy3도 통과)
import sys
input = sys.stdin.readline
N = int(input())
num = list(map(int, input().split()))
op = list(map(int, input().split())) # +, -, *, //
maximum = -1e9
minimum = 1e9
def dfs(depth, total, plus, minus, multiply, divide):
global maximum, minimum
if depth == N:
maximum = max(total, maximum)
minimum = min(total, minimum)
return
if plus:
dfs(depth + 1, total + num[depth], plus - 1, minus, multiply, divide)
if minus:
dfs(depth + 1, total - num[depth], plus, minus - 1, multiply, divide)
if multiply:
dfs(depth + 1, total * num[depth], plus, minus, multiply - 1, divide)
if divide:
dfs(depth + 1, int(total / num[depth]), plus, minus, multiply, divide - 1)
dfs(1, num[0], op[0], op[1], op[2], op[3])
print(maximum)
print(minimum)확실히 DFS라는 효과적인 알고리즘을 이용하니 시간복잡도면에서 이점을 많이 가져갈 수 있었다.
728x90
