백준 14888 연산자 끼워넣기

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

14888번: 연산자 끼워넣기

 

처음에 permu어쩌구를 통해 모든 기호의 배열을 구해서 풀었다.

 

from itertools import permutations
import sys
input=sys.stdin.readline
n=int(input())
a=[*map(int,input().split())]
q,w,e,r=map(int,input().split())
tmp_sign='+'*q+'-'*w+'*'*e+'/'*r
signs=list(permutations(tmp_sign,n-1))
signs=list(set(signs))
max_answer=-1000000000
min_answer=1000000000

for sign in signs:
    answer=a[0]
    for i in range(n-1):
       
        if sign[i]=='+': 
            answer+=a[i+1]
        elif sign[i]=='-': 
            answer-=a[i+1]
        elif sign[i]=='*': 
            answer*=a[i+1]
        elif sign[i]=='/': 
            # answer//=a[i+1]
            if answer>=0:
                answer//=a[i+1]
            else:
                answer= -(-answer//a[i+1])


    min_answer=min(min_answer,answer)
    max_answer=max(max_answer,answer)

print(max_answer,min_answer,sep='\n')

근데 다른 풀이를 보니 그럴거없이

그냥 dfs?로 4경위의 수를 모두 구해서 풀면된다.

만일 주어진 기호를 다 썼다면, 그 기호를 뺀 다른기호만 생각한다.

import sys
input=sys.stdin.readline

def solve(idx,value):
    global max_value
    global min_value
    if idx==n:
        max_value=max(max_value,value)
        min_value=min(min_value,value)
        return

    for i in range(4):
        if sign[i]==0:
            continue

        if i==0:
            sign[i]-=1
            tmp=value+a[idx]
        
        elif i==1:
            sign[i]-=1
            tmp=value-a[idx]

          
        elif i==2:
            sign[i]-=1
            tmp=value*a[idx]

          
        else :
            sign[i]-=1
            if value>0:
                tmp=value//a[idx]
            else:
                tmp=-(-value//a[idx])

        solve(idx+1,tmp)
        sign[i]+=1



n=int(input())
a=[*map(int,input().split())]
sign=[*map(int,input().split())]
max_value=-1000000000
min_value=1000000000
    
        
solve(1,a[0])

print(max_value,min_value,sep='\n')

이러니깐 시간차이가 거의 10배가난다.

다시 돌아오지 않고 계산만 하면 더빠를듯