[백준] 14888번(연산자 끼워넣기)

백준 14888번

최종 제출 코드

n = int(input())
values = list(map(int, input().split()))
array = list(map(int, input().split()))

visited = [0, 0, 0, 0]
max_value = -1000000000
min_value = 1000000000
stack = []

# 값을 계산하는 함수
def calculate(value, number):

  if stack[-1] == 0:
    return value + values[number]
  elif stack[-1] == 1:
    return value - values[number]
  elif stack[-1] == 2:
    return value * values[number]
  else:
    return int(value/values[number])


# 기호의 순열을 생성하는 함수(깊이 우선 탐색)
def dfs(value):

  global max_value, min_value

  if len(stack) > 0:
    value = calculate(value, sum(visited))

  if sum(visited) == sum(array):
    max_value = max(max_value, value)
    min_value = min(min_value, value)
    return

  for i in range(len(array)):
    if visited[i] < array[i]:
      visited[i] += 1
      stack.append(i)
      dfs(value)
      visited[i] -= 1
      stack.pop()


# 결과값 출력
dfs(values[0])
print(max_value)
print(min_value)

◼️ dfs를 활용하여 연산자의 순열을 만든다

• visited에 등장 횟수를 저장해주며, 각각의 등장 횟수에 맞춰 순열 생성
• stack의 길이가 주어진 연산자의 개수와 일치(혹은 n-1과 일치)하면 max_value, min_value 값을 업데이트하고 return
• 연산을 실행하는 함수를 따로 만들어 분리

다른 방법?

• 다른 사람들이 짠 코드를 보니 나처럼 연산을 실행하는 함수를 따로 만들거나 stack에 연산자를 저장하는게 아니라 아예 dfs 함수에 인수로 전달!
• 코드가 확실히 더 깔끔한 것 같다

수정한 코드

n = int(input())
values = list(map(int, input().split()))
array = list(map(int, input().split()))

max_value = -1000000000
min_value = 1000000000


def dfs(value, index, plus, minus, multiple, divide):

  global max_value, min_value

  if index==n-1:
    max_value = max(max_value, value)
    min_value = min(min_value, value)
    return
    
  if plus:
    dfs(value+values[index+1], index+1, plus-1, minus, multiple, divide)
  if minus:
    dfs(value-values[index+1], index+1, plus, minus-1, multiple, divide)
  if multiple:
    dfs(value*values[index+1], index+1, plus, minus, multiple-1, divide)
  if divide:
    dfs(int(value/values[index+1]), index+1, plus, minus, multiple, divide-1)

dfs(values[0], 0, array[0], array[1], array[2], array[3])
print(max_value)
print(min_value)