[백준] 연산자 끼워넣기

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

14888번: 연산자 끼워넣기

 

DFS 알고리즘을 이용하여 모든 경우를 구하여 최댓값과 최솟값을 반환하면 된다.

연산자의 개수는 len(A) - 1 이기 때문에 rf() 의 인자 i 가 len(A) 일 때 하나의 계산이 끝나므로 그때의 값을 비교하면 된다.

 

o[] 로 해당 연산을 할 수 있는지 알 수 있다. rf() 가 시작할 때 해당 연산자를 썼다는 의미로 -1을 해주고 끝나면 이 전의 o[] 로 돌려주기 위해 +1를 해준다.

 

import sys

N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))
o = list(map(int, sys.stdin.readline().split()))
m, M = float('inf'), float('-inf')

def rf(A, o, n, i):
    global m
    global M
    
    if len(A) == i:
        m = min(m, n)
        M = max(M, n)
    else:
        for k in range(4):
            if k == 0 and o[k] > 0:
                o[k] -= 1
                rf(A, o, n + A[i], i + 1)
                o[k] += 1
            
            if k == 1 and o[k] > 0:
                o[k] -= 1
                rf(A, o, n - A[i], i + 1)
                o[k] += 1
            
            if k == 2 and o[k] > 0:
                o[k] -= 1
                rf(A, o, n * A[i], i + 1)
                o[k] += 1
            
            if k == 3 and o[k] > 0:
                o[k] -= 1
                rf(A, o, n // A[i] if n > 0 else (- n // A[i]) * - 1, i + 1)
                o[k] += 1

rf(A, o, A[0], 1)
    
print(M)
print(m)