[n14888] 연산자 끼워넣기 in python

 

이 문제도 역시나 백트래킹

python3로 돌리면 시간초과가 나서

pypy3로 돌렷다 ㅠㅠ

그래도 시간이 많이 나오긴 하는데

효율적인 코드를 좀 뒤져봐야 할 것 같다! 

 

 

n = int(input())
array = list(map(int, input().split()))
operator = list(map(int, input().split()))  # +, -, *, //
str_operator = []
for idx, i in enumerate(operator):
    if idx == 0:
        for j in range(i):
            str_operator.append('+')
            continue
    elif idx == 1:
        for j in range(i):
            str_operator.append('-')
            continue
    elif idx == 2:
        for j in range(i):
            str_operator.append('*')
            continue
    elif idx == 3:
        for j in range(i):
            str_operator.append('//')
            continue

answer = set()
operator_len = len(str_operator)
visited = [0 for _ in range(operator_len)]
now = array[0]

def cal(n1, n2, oper):
    if oper == '+':
        return n1 + n2
    elif oper == '-':
        return n1 - n2
    elif oper == '*':
        return n1 * n2
    else:
        if n1 < 0:
            n1 = -n1
            return -(n1 // n2)
        else:
            return n1 // n2

def dfs(depth, now):
    if operator_len == depth:
        # 끝에 다다른 경우
        answer.add(now)
        return
    for i in range(operator_len):
        if visited[i]:  # 이미 방문했을 경우 = 건너뛰기 과정
            continue
        visited[i] = 1
        temp = now
        now = cal(temp, array[depth+1], str_operator[i])
        dfs(depth + 1, now)
        visited[i] = 0
        now = temp


dfs(0, now)
print(max(answer))
print(min(answer))