[백준] 14888 연산자 끼워넣기

https://acmicpc.net/problem/14888 

14888번: 연산자 끼워넣기

n = int(input())
n_list = list(map(int, input().split()))
operator = list(map(int, input().split()))
min_val = 1000000000
max_val = -1000000000
def backtrack(index, number=n_list[0]):
    if index == n - 1:
        global min_val, max_val
        if min_val > number:
            min_val = number
        if max_val < number:
            max_val = number
        return
    else:
        if operator[0]:
            operator[0] -= 1
            backtrack(index + 1, number + n_list[index + 1])
            operator[0] += 1
        if operator[1]:
            operator[1] -= 1
            backtrack(index + 1, number - n_list[index + 1])
            operator[1] += 1
        if operator[2]:
            operator[2] -= 1
            backtrack(index + 1, number * n_list[index + 1])
            operator[2] += 1
        if operator[3] and n_list[index + 1]:
            operator[3] -= 1
            backtrack(index + 1, int(number / n_list[index + 1]))
            operator[3] += 1

backtrack(0)
print(max_val,min_val, sep='\n')

이전에 풀었던 문제들처럼 pypy에서만되고 python에서 안될줄 알았는데 오히려 python에서 더 빨랐다.

백트래킹을 사용해서 모든 조합을 확인하는 방법으로 진행했다

나누기 부분에서 조금 시간이 걸렸다.

예제 3번에서 max값이 계속 48이 나왔는데 나누기 연산자를 '//' 로 하면 음수일때 원하는 값이 나오지 않는다.

그래서 나누고 '/'를 사용했더니 성공하였다.