[알고리즘] 백준 14888 - 연산자 끼워넣기 (파이썬)

오랜만에 내 힘으로 푼 문제. 

처음에 순열 라이브러리를 사용해서 모든 경우의 수를 구해야 겠다고 생각하다가.. 시간 초과가 예상되어 DFS로 풀이했다.

아래는 풀이 코드이다.

from sys import stdin as s

def DFS(index, sum):
    global A, operators

    if index == len(A) - 1 :
        ans.append(sum)
        return
    else:
        # 재귀적으로 DFS 탐색 시작
        # 덧셈, 뺄셈, 곱셈, 나눗셈 4가지 경우의 수. (operator 배열의 인덱스 순)
        for i in range(4):
            # 횟수가 남아있다면
            if operators[i] > 0:
                if i == 0:
                    operators[i] -= 1
                    DFS(index + 1, sum + (A[index + 1]))
                    operators[i] += 1
                elif i == 1:
                    operators[i] -= 1
                    DFS(index + 1, sum - (A[index + 1]))
                    operators[i] += 1
                elif i == 2:
                    operators[i] -= 1
                    DFS(index + 1, sum * (A[index + 1]))
                    operators[i] += 1
                elif i == 3:
                    operators[i] -= 1
                    if sum < 0 :
                        DFS(index + 1, -(abs(sum) // (A[index + 1])))
                        operators[i] += 1
                    else:
                        DFS(index + 1, sum // (A[index + 1]))
                        operators[i] += 1

if __name__ == "__main__":
    n = int(s.readline().rstrip())
    A = list(map(int, s.readline().rstrip().split()))
    operators = list(map(int, s.readline().rstrip().split()))

    ans = []

    DFS(0, A[0])

    print(max(ans), min(ans), sep="\n")