백준 14888번

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

14888번: 연산자 끼워넣기

n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

total_min = 1e9
total_max = -1e9

def dfs(i,cur):
  global  total_min,total_max

	#연산자의 개수만큼 재귀 최대값 최소값 구하기
  if i == n:
    total_max = max(total_max,cur)
    total_min = min(total_min,cur)

  else:
    #더하기
    if b[0] >0:
      b[0] -=1
      dfs(i+1, cur +a[i])
      b[0] +=1
    #빼기
    if b[1]>0:
      b[1]-=1
      dfs(i+1, cur-a[i])
      b[1]+=1
    #곱하기
    if b[2]>0:
      b[2]-=1
      dfs(i+1, cur*a[i])
      b[2]+=1
    #나누기
    if b[3]>0:
      b[3]-=1
      dfs(i+1, int(cur/a[i]))
      b[3]+=1

dfs(1,a[0])



print(total_max)
print(total_min)

 

연산자의 개수의 조합을 다양하게 하여 문제를 푸는 것이 중요

 

따라서 DFS를 사용하여

더하기,빼기, 곱하기, 나누기의 개수를 조합하여 값을 구하고

그 과정에서 가장 큰 값과 작은 값을 구해줌