백준 14888번_연산자 끼워넣기 [python/파이썬

# argument를 3개 사용한 경우

num = int(input())
num_list = list(map(int, input().split()))
plus, minus, multi, division = map(int, input().split())
 
max_result = -1000000000
min_result = 1000000000
 
N = plus+minus+multi+division
check_list = [False]*N
count = 0
index = 0
result_list = []
 
def permutation(count, index, result):
    global max_result, min_result
    if count == N:
        if result > max_result:
            max_result = result
        if result < min_result:
            min_result = result
        return
 
    for i in range(N):
        if check_list[i] == True:
            continue
 
        check_list[i] = True
        if i <= plus - 1:
            permutation(count + 1, index + 1, result+num_list[index])
        elif i <= plus + minus - 1:
            permutation(count + 1, index + 1, result-num_list[index])
        elif i <= plus + minus + multi - 1:
            permutation(count + 1, index + 1, result*num_list[index])
        elif i <= plus + minus + multi + division - 1:
            if result < 0:
                permutation(count + 1, index + 1, -((-result)//num_list[index]))
            else:
                permutation(count + 1, index + 1, result//num_list[index])
        check_list[i] = False
 
permutation(0,1, num_list[0])
print(max_result)
print(min_result)

 

 이전의 N과 M 문제처럼 백트랙킹을 이용하여  문제를 해결할 수 있다. 그러나 이 python3로 해당 코드를 제출할 경우 시간 초과에 걸리게 된다. 반면 PyPy3로 코드를 제출하면 통과할 수 있는데 이는 PyPy3의 속도가 python3보다 빠르기 때문이다. (둘이 같은 코드를 내도 무관)

 

 

# argument를 6개 사용하는 경우

num = int(input())
num_list = list(map(int, input().split()))
plus, minus, multi, division = map(int, input().split())
 
max_result = -1000000000
min_result = 1000000000
 
N = plus+minus+multi+division
 
def permutation(count, plus, minus, multi, division, result):
    global max_result, min_result
    if count == N:
        if result > max_result:
            max_result = result
        if result < min_result:
            min_result = result
        return
 
    if plus > 0:
        permutation(count + 1, plus-1, minus, multi, division, result+num_list[count+1])
    if minus > 0:
        permutation(count + 1, plus, minus-1, multi, division, result-num_list[count+1])
    if multi > 0:
        permutation(count + 1, plus, minus, multi-1, division, result*num_list[count+1])
    if division > 0:
        if result < 0:
            permutation(count + 1, plus, minus, multi, division-1, -((-result)//num_list[count+1]))
        else:
            permutation(count + 1, plus, minus, multi, division-1, result//num_list[count+1])
 
permutation(0,plus, minus, multi, division, num_list[0])
print(max_result)
print(min_result)

 

 앞의 코드와는 다르게 해당 코드는 python3로 코드를 제출해도 시간제한에 걸리지 않고 통과한다. 앞의 코드에서는 for문을 돌며 재귀적으로 함수를 호출한 반면 해당 코드는 반복문이 없기 때문이다. 대신 argument의 개수가 늘어났지만 늘어난 argument가 모두 int형으로 메모리에 영향을 주지 않는다. 오히려 tail_recursion처럼 arument의 개수가 늘어날수록 시간 복잡도가 개선되는 모양이다.