https://www.acmicpc.net/problem/14888
14888번: 연산자 끼워넣기첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, …, AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수,www.acmicpc.net
처음에 permu어쩌구를 통해 모든 기호의 배열을 구해서 풀었다.
from itertools import permutationsimport sysinput=sys.stdin.readline
n=int(input())a=[*map(int,input().split())]q,w,e,r=map(int,input().split())
tmp_sign='+'*q+'-'*w+'*'*e+'/'*rsigns=list(permutations(tmp_sign,n-1))
signs=list(set(signs))max_answer=-1000000000min_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 sysinput=sys.stdin.readlinedef 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=-1000000000min_value=1000000000 solve(1,a[0])
print(max_value,min_value,sep='\n')이러니깐 시간차이가 거의 10배가난다.
다시 돌아오지 않고 계산만 하면 더빠를듯