[알고리즘] 백준 14888 연산자 끼워넣기 파이썬

백준 14888 연산자 끼워넣기 파이썬

 

문제

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

14888번: 연산자 끼워넣기

 

 

 

접근법

연산자들을 중복을 제거하여 순서대로 줄세우는게 관건이다.

12345 를 순서대로 줄 세운다면, 경우의 수는 

5! = 5*4*3*2*1 = 120 이다.

만약 11234 라면 ? 

5!/2 = 5*4*3*2*1/2 = 60 이다. 수학의정석 10-가 였나? 공부했던 기억이 난다.

중복을 제거하는 것은 뒷 순위로 두고, 첫 단계로 입력받은 연산자들을 0123(+-*/) 로 매핑하고

배열을 출력해보았다. 여기서 DFS를 썼다.

 

조건을 추가하여, 배열을 하나 더 두고 append pop 하면서 같이 연산하며 중복을 제거해주었다.

마지막으로 c++ 의 나누기 연산은 -1/3 =0 이고 파이썬은 -1/3=-1 이다. 이것만 분기해서 처리해주면 끝

 

 

소스코드

N=int(input())
num=list(map(int,input().split()))
k=list(map(int,input().split())) # + - * /
if N<5:
    a=[0]*4
else:
    a=[0]*(N-1)
arr=[]
ans=[]
def cal(c):
    tmp=num[0]
    for i in range(N-1):
        if c[i]==0:
            tmp+=num[i+1]
        elif c[i]==1:
            tmp-=num[i+1]
        elif c[i]==2:
            tmp*=num[i+1]
        elif c[i]==3:
            tt=tmp%num[i+1]
            tmp//=num[i+1]
            if tmp <0 and tt!=0:
                tmp+=1
    ans.append(tmp)

def dfs():
    if sum(a)==sum(k):
        #print(arr)
        cal(arr)
        return
    
    for i in range(4):
        if k[i]!=0 and k[i]-a[i]!=0:
            arr.append(i)
            a[i]+=1
            dfs()
            arr.pop()
            a[i]-=1
dfs()
print(max(ans))
print(min(ans))