백준 14888번 연산자 끼워넣기

 

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

14888번: 연산자 끼워넣기

이거 왜 재귀로 풀 생각을 못했을까? 나중에 한번 더 풀어야겠다.

보자마자 그냥 순열 박아버렸는데 dfs로도 풀던데 왜 생각을 못했을까?

암튼 순열을 통해 iterative하게 푸는 방법이 조금 나이브한 접근인데 recursive한 방법이 아무래도 조금 더 컴퓨터적 사고능력에 가깝지 않나 싶다.

아래는 순열을 통해 푸는거다.

#순열+반복문
import sys
import itertools
from math import inf
n = int(sys.stdin.readline())-1 
num_array = list(map(int,sys.stdin.readline().split()))
oper = list(map(int,sys.stdin.readline().split()))
m,M = inf,-inf
o = ''
for i,j in zip(oper,['+','-','*','/']):
	o+=j*i
operators = set(itertools.permutations(o,n))
for operator in operators:
    s = num_array[0]
    for n,o in zip(num_array[1:],operator):
        if o=='+':
        	s+=n
        elif o =='-':
        	s-=n
        elif o =='*':
        	s*=n
        else:
        	s = -(-s//n) if s<0 else s//n
    m,M=min(m,s),max(M,s)
print(M)
print(m)

이건 재귀로 푸는건데 뭔가 뭔가다... 은근 코드가 지저분함

#재귀+dfs
import sys
r = sys.stdin.readline
n = int(r().strip())
num_array = list(map(int,r().split()))
oper = list(map(int,r().split()))
m,M = 1e9,-1e9
def f(num, index, add, sub, mul, div):
    global m,M
    if index==n-1:
        m= min(num,m)
        M = max(num,M)
        return None
    index+=1
    if add>0:
        f(num+num_array[index], index, add-1, sub, mul, div)
    if sub>0:
        f(num-num_array[index], index, add, sub-1, mul, div)
    if mul>0:
        f(num*num_array[index],index, add, sub, mul-1, div)
    if div>0:
        f(num//num_array[index] if num>0 else -(-num//num_array[index]), index, add, sub, mul, div-1)
f(num_array[0],0,*oper)
print(M)
print(m)