[백준/Python] 14888번 - 연산자 끼워넣기

문제

백준 14888번 - 연산자 끼워넣기

해결 과정

• 숫자는 고정된 상태에서 연산자 순서를 변경해서 최소,최대값을 확인하는 것
  • 모든 경우의 수를 구하지 않고 하는 방법이 있을까?
  • 쉽지 않다 -> DFS/BFS, 완전탐색을 생각해보자
• 가능한 모든 경우의 수를 다 계산하기
  • 백트래킹
  • 브루트포스/완전탐색

시행착오

• 백트래킹 개념을 확실히 할 필요가 있다

풀이

import sys

n = int(sys.stdin.readline())
num = list(map(int,sys.stdin.readline().split()))
cal = list(map(int,sys.stdin.readline().split())) # +, -, *, //

maximum = -1e9
minimum = 1e9

def dfs(depth, total, plus, minus, mul, div):
  global maximum, minimum
  if depth == n:
    maximum = max(total,maximum)
    minimum = min(total,minimum)
    return
  if plus:
    dfs(depth + 1, total + num[depth], plus - 1, minus, mul, div)
  if minus:
    dfs(depth + 1, total - num[depth], plus, minus - 1, mul, div)
  if mul:
    dfs(depth + 1, total * num[depth], plus, minus, mul - 1, div)
  if div:
    dfs(depth + 1, int(total / num[depth]), plus, minus, mul, div - 1)
  
    
dfs(1,num[0],cal[0],cal[1],cal[2],cal[3])
print(maximum)
print(minimum)