연산자 끼워넣기

https://www.acmicpc.net/problem/14888

# p349

n = int(input())
numbers = list(map(int, input().split()))
plus, minus, multi, divide = map(int, input().split())
biggest = -100000000
smallest = 1000000001

def dfs(nn, i, total):
    global plus, minus, multi, divide, biggest, smallest
    if nn == i:
        if total > biggest:
            biggest = total
        if total < smallest:
            smallest = total
    else:
        if plus > 0:
            plus -= 1
            dfs(nn, i+1, total + numbers[i])
            plus += 1
        if minus > 0:
            minus -= 1
            dfs(nn, i+1, total - numbers[i])
            minus += 1
        if multi > 0:
            multi -= 1
            dfs(nn, i+1, total * numbers[i])
            multi += 1
        if divide > 0:
            divide -= 1
            dfs(nn, i+1, int(total / numbers[i]))
            divide += 1
        
        
dfs(n, 1, numbers[0])
print(biggest, smallest, sep='\n')

문제를 처음보고 뭐 이렇게 쉬운 문제가 있지 하면서 풀었더니 너무 헤맸던 것 같다. 맨 처음에는 연산자 경우의 수를 permutations를 이용해서 반복하는 식으로 풀었는데, 아예 접근방식 자체가 잘못됐었다. 이코테의 답안을 참고해보니 product를 이용하면 된다고 한다. 나는 이코테 해설을 참고하여 dfs로 풀었다. 연산자의 개수를 다시 유지시켜야 하는데 이를 dfs가 끝나고 다시 채워주는게 관건이었다. 뭔가 dfs를 굳이 안써도 완전탐색으로도 풀 수 있는 문제같다.