BOJ 14888번: 연산자 끼워넣기

www.acmicpc.net/problem/14888

14888번: 연산자 끼워넣기

문제풀이:

모든 경우를 탐색해야 하므로 DFS를 이용하여 풀 수 있다.

연산자를 주어진 배열의 형태로 접근해 보려고 하다가.. 어차피 위치는 정해져 있으니까 개수만 가져와서 함수를 만들었다. DFS 구현 부분에서 elif라고 적었다가 오류가 났었다.. 간단하게 풀 수 있는 문제인데 너무 어렵게 생각했던 것 같다.

 

import sys
input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split()))
cal = list(map(int, input().split()))

maxAns = -9999999999
minAns = 9999999999

def solve(plus, minus, mul, div, cnt, temp):
    global maxAns
    global minAns
    if (cnt==N-1):
        maxAns = max(maxAns, temp)
        minAns = min(minAns, temp)

    else:
        if (plus>0): solve(plus-1, minus, mul, div, cnt+1, temp+A[cnt+1])
        if (minus>0): solve(plus, minus-1, mul, div, cnt+1, temp-A[cnt+1])
        if (mul>0): solve(plus, minus, mul-1, div, cnt+1, temp*A[cnt+1])
        if (div>0):
            if (temp<0):
                temp = temp*(-1)//A[cnt+1]
                solve(plus, minus, mul, div-1, cnt+1, temp*(-1))
            else:
                solve(plus, minus, mul, div-1, cnt+1, temp//A[cnt+1])

solve(cal[0], cal[1], cal[2], cal[3], 0, A[0])
print(maxAns)
print(minAns)