[python] 14888. 연산자 끼워넣기

문제 출처

14888. 연산자 끼워넣기

 

풀이

이 문제는 최솟값과 최댓값을 모두 출력해야 하므로 가능한 모든 경우를 다 계산해 봐야 한다. 최악의 경우는 10! / (4!4!3!) 로 주어진 시간안에 충분히 해결 가능하다.

 

N = int(input())
nums = list(map(int, input().split()))
add, sub, mul, div = map(int, input().split())

min_, max_ = 1e9, -1e9

def dfs(i, res, add, sub, mul, div):
    global max_, min_
    if i == N:
        max_ = max(res, max_)
        min_ = min(res, min_)
        return

    else:
        if add:
            dfs(i+1, res+nums[i], add-1, sub, mul, div)
        if sub:
            dfs(i+1, res-nums[i], add, sub-1, mul, div)
        if mul:
            dfs(i+1, res*nums[i], add, sub, mul-1, div)
        if div:
            dfs(i+1, int(res/nums[i]), add, sub, mul, div-1)

dfs(1, nums[0], add, sub, mul, div)
print(max_)
print(min_)