https://www.acmicpc.net/problem/14888
n=int(input())
arr=list(map(int,input().split()))
oper=list(map(int,input().split()))
def custom_division(a, b):
if a>0:
return a//b
else:
a=-a
return -(a//b)
def dfs(n,arr,oper,depth,result):
global max_value,min_value
if depth==n-1:
max_value=max(max_value,result)
min_value=min(min_value,result)
return
if oper[0]>0:
oper[0]-=1
dfs(n,arr,oper,depth+1,result+arr[depth+1])
oper[0]+=1
if oper[1]>0:
oper[1]-=1
dfs(n,arr,oper,depth+1,result-arr[depth+1])
oper[1]+=1
if oper[2]>0:
oper[2]-=1
dfs(n,arr,oper,depth+1,result*arr[depth+1])
oper[2]+=1
if oper[3]>0:
oper[3]-=1
dfs(n,arr,oper,depth+1,custom_division(result,arr[depth+1]))
oper[3]+=1
result=arr[0]
max_value=-int(1e9)
min_value=int(1e9)
dfs(n,arr,oper,0,result)
print(max_value)
print(min_value)
숫자와 연산자의 갯수가 10개 정도이기 때문에 모든 경우의 수를 구하며 탐색하는 백트래킹을 생각할 수 있다. 이 때, 연산의 결과도 최대 값이 10억 이하 -10억이 나올 수 있기 때문에 최대 최솟값도 10억을 기준으로 맞추어놓아야 제대로 된 정답을 도출할 수 있다.
각 연산자를 부여하면서 해당 결과값을 남은 연산자가 없을 때까지 수행하고 깊이를 깊게하면 된다. 그러다가 원하는 만큼의 깊이, 즉 모든 연산자가 소진되고 숫자가 계산되었을 때를 기준으로 값을 기준으로 최대, 최소값을 갱신하면 된다.
나누기 연산의 경우, 이 문제의 한하여 음수의 연산을 따로 다루고 있기 때문에 이 점에 유의하여 풀면된다.
이렇게 Python으로 백준의 "연산자 끼워넣기" 문제를 해결해보았습니다. 코드와 개념 설명을 참고하여 문제를 해결하는 데 도움이 되셨길 바랍니다! 😊