백준 / 14888번 / 연산자 끼워넣기 / python 파이썬 / 백트래킹

 

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

 

 

 

코드

N = int(input())
nums = list(map(int, input().split()))
op = list(map(int, input().split()))

maxn = -1e9
minn = 1e9

def dfs(n, i, add, sub, mul, div):
    global maxn, minn

    if i == N:
        maxn = max(maxn, n)
        minn = min(minn, n)
        return
    else:

        if add:
            dfs(n + nums[i], i+1, add - 1, sub, mul, div)

        if sub:
            dfs(n - nums[i], i+1, add, sub - 1, mul, div)

        if mul:
            dfs(n * nums[i], i+1, add, sub, mul - 1, div)

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

dfs(nums[0], 1, op[0], op[1], op[2], op[3])

print(maxn)
print(minn)

 

알게된 것

 

이 문제는 연산자의 모든 조합의 경우를 생각하며 최댓값과 최솟값을 구해야하기 때문에 브루트포스의 문제에 속한다. 하지만 itertools의 combinations, permutations 등을 이용하면 시간초과가 발생한다. 따라서 백트래킹(DFS)의 재귀를 활용해서 문제를 풀어야 한다. 

 

또한 문제의 조건과 같이 음수의 나눗셈 처리 시, 몫을 C++14의 기준을 따르게 하기 위해 int()를 사용하여 조건을 만족시킬 수 있다.