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

Problem

연산자의 개수를 수 사이에 결합하여 최댓값과 최솟값을 구하는 문제

Solution

DFS를 이용하여 탐색후 최대,최솟값 구하기

코드설명

1) 깊이 1, 배열 첫값, 연산자 각 횟수들을 DFS 호출
첫값을 연산 전에 넣어줘야 하므로 depth 1 합은 배열0인덱스 값으로 호출

2)4가지의 dfs 경우를 통해 연산자 개수를 하나씩 없애면서 각각의 연산에 대해 계산을 해주고 다시 DFS

Python Code

import sys

N=int(sys.stdin.readline())
arrList=list(map(int,sys.stdin.readline().split()))
math=list(map(int,sys.stdin.readline().split()))
maxnum=-1e9
minnum=1e9
def dfs(depth,sum,plus,minus,multiply,divide):
    global maxnum
    global minnum
    if depth==N:
        maxnum=max(sum,maxnum)
        minnum=min(sum,minnum)
    else:
        if plus:
            dfs(depth+1,sum+arrList[depth],plus-1,minus,multiply,divide)
        if minus:
            dfs(depth+1,sum-arrList[depth],plus,minus-1,multiply,divide)
        if multiply:
            dfs(depth+1,sum*arrList[depth],plus,minus,multiply-1,divide)
        if divide:
            dfs(depth+1,int(sum/arrList[depth]),plus,minus,multiply,divide-1)
dfs(1,arrList[0],math[0],math[1],math[2],math[3])

print(maxnum)
print(minnum)