[백준][DFS][순열] 14888. 연산자 끼워넣기

14888. 연산자 끼워넣기

14888번: 연산자 끼워넣기

• dfs로 푸는 방법 알아두기

https://yygs321.tistory.com/265 와 동일한 문제지만, sw 문제에서는 순열로는 해결 x DFS만 가능

 

• 내 풀이 - 순열
  • 최댓값, 최솟값 초기 설정 : -1e9, 1e9 안하면 오답

from itertools import permutations 

def operate(n1,n2,o):
    if o=='+':
        return n1+n2
    elif o=='-':
        return n1-n2
    elif o=='*':
        return n1*n2
    else:
        return int(n1/n2)
          
n=int(input())
operator="+-*/"
num=list(map(int,input().split())) #숫자 
lst=list(map(int,input().split())) #연산자

op=""

for idx,ls in enumerate(lst):
    op+=operator[idx]*ls

#set으로 중복 제거
#연산자 개수: n-1
pmt=set(permutations(op,n-1))

first=num.pop(0) #하나 줄여서 연산자랑 개수 맞춤

max_val,min_val=-1e9, 1e9
for pm in pmt:
    result=first #매연산 돌아갈때 첫숫자부터 다시 계산
    for n, p in zip(num, pm):
        result=operate(result, n, p)
      
    max_val=max(max_val,result)
    min_val=min(min_val,result)

print(max_val)
print(min_val)

 

 

• 다른 풀이: DFS
  • dfs로 푸는 방법 알아둬야함

import sys

input = sys.stdin.readline
N = int(input())
num = list(map(int, input().split()))
op = list(map(int, input().split()))  # +, -, *, //

maximum = -1e9
minimum = 1e9


def dfs(depth, total, plus, minus, multiply, divide):
    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, multiply, divide)
    if minus:
        dfs(depth + 1, total - num[depth], plus, minus - 1, multiply, divide)
    if multiply:
        dfs(depth + 1, total * num[depth], plus, minus, multiply - 1, divide)
    if divide:
        dfs(depth + 1, int(total / num[depth]), plus, minus, multiply, divide - 1)


dfs(1, num[0], op[0], op[1], op[2], op[3])
print(maximum)
print(minimum)