연산자 끼워 넣기

풀이

  이 문제는 주어진 조건 속에 실마리가 있다. 입력값 n(2<=n<=11)의 범위가 매우 작으므로 완전탐색의 가능성이 크다. 완전탐색을 생각해 보면서 문제를 해석해보면 이 문제는 각 사칙연산을 중복해서 나열해서 수식의 최대값, 최소값을 구하는, 즉 중복 순열 문제라는 것을 어렵지 않게 파악할 수 있다. 파이썬에서는 중복 순열(product) 라이브러리를 제공해 주지만 나는 dfs를 이용해서 중복 순열을 구현했다.

n = int(input())
data = list(map(int, input().split()))
add, sub, mul, div = map(int, input().split())

max_value = int(-1e9)
min_value = int(1e9)

def dfs(index, element):
    global max_value, min_value, add, sub, mul, div
    if index == n-1:
        max_value = max(max_value, element)
        min_value = min(min_value, element)
        return

    # case : +
    if add >0:
        add -= 1
        dfs(index+1, element + data[index+1])
        add += 1
    # case : -
    if sub >0:
        sub = sub -1
        dfs(index+1, element - data[index+1])
        sub = sub + 1
    # case : *
    if mul >0:
        mul = mul - 1
        dfs(index+1, element * data[index+1])
        mul = mul +1
    # case : //
    if div >0:
        div = div -1
        dfs(index+1, int(element/data[index+1]))
        div = div +1

dfs(0, data[0])
print(max_value)
print(min_value)

시간복잡도 : O(4^n)