[백준] 14888 연산자 끼워넣기 (파이썬 python)

 

 

문제 링크

 

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

14888번: 연산자 끼워넣기

 

 

문제

 

 

 

 

 

 

문제 풀이

 

 

import sys

n = int(sys.stdin.readline())
nums = list(map(int, sys.stdin.readline().split()))
operator = list(map(int, sys.stdin.readline().split()))

maximum = -1e9
minimum = 1e9


def dfs(cnt, result, plus, minus, multiply, divide):
    global maximum, minimum
    if cnt == n:
        maximum = max(result, maximum)
        minimum = min(result, minimum)
        return

    if plus:
        dfs(cnt + 1, result + nums[cnt], plus - 1, minus, multiply, divide)
    if minus:
        dfs(cnt + 1, result - nums[cnt], plus, minus - 1, multiply, divide)
    if multiply:
        dfs(cnt + 1, result * nums[cnt], plus, minus, multiply - 1, divide)
    if divide:
        dfs(cnt + 1, int(result / nums[cnt]), plus, minus, multiply, divide - 1)


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

print(maximum)
print(minimum)

 

 

재귀 함수를 활용해서 풀이했다.

연산자가 0보다 클 경우 해당 연산을 하도록 하고, 모든 수를 다 썼을 경우

결과값과 현재의 최댓값, 최솟값을 return 해주는 것을 반복한다!