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

132. 연산자 끼워넣기

1) 어떤 전략(알고리즘)으로 해결?

(1) 우선 연산자의 경우의 수를 출력
(아래는 경우의 수 잘 나오나 체크해보기 위해 res안에 있는 애들 프린트하게 한 것)

import sys
def perm(N):
    if N==n-1:
        for i in res:
            print(i,end=" ")
        print()

    else :
        for i in range(4):#연산자의 갯수만큼(op의 인덱스 0 1 2 3 검사해야함)
            if op[i]>0:#연산자가 존재한다면
                res.append(i) #연산자 인덱스를 res에 저장 0 1 2 3 / 덧 뺄 곱 나
                op[i]-=1
                perm(N+1)
                res.pop()
                op[i]+=1
            
if __name__=="__main__":
    n=int(input())
    data=list(map(int,sys.stdin.readline().split()))
    op=list((map(int,sys.stdin.readline().split())))#무조건 n-1개 연산자가 주어짐)
    chk=[0]*(n)
    res=[]
    perm(0)

(2) - 그 다음 연산자에 따라서 적절한 연산이 값에 수행되도록 하기

import sys
def perm(N):
    global datat,mini,maxi
    if N==n-1:
        tot=data[0]
        for i in range(n-1) :
            if res[i]==0:#덧셈
                tot+=data[i+1]
            elif res[i]==1:#뺄셈
                tot-=data[i+1]
            elif res[i]==2:#곱셈
                tot*=data[i+1]
            else : #나눗셈
                if tot<0:
                    tot=-((-tot)//data[i+1])
                else : 
                    tot//=data[i+1]

        if tot<mini:
            mini=tot
        if tot>maxi:
            maxi=tot

    else :
        for i in range(4):#연산자의 갯수만큼(op의 인덱스 0 1 2 3 검사해야함)
            if op[i]>0:#연산자가 존재한다면
                res.append(i) #연산자 인덱스를 res에 저장 0 1 2 3 / 덧 뺄 곱 나
                op[i]-=1
                perm(N+1)
                res.pop()
                op[i]+=1

2) 코딩 설명

<내 풀이>

import sys
def perm(N):
    global datat,mini,maxi
    if N==n-1:
        tot=data[0]
        for i in range(n-1) :
            if res[i]==0:#덧셈
                tot+=data[i+1]
            elif res[i]==1:#뺄셈
                tot-=data[i+1]
            elif res[i]==2:#곱셈
                tot*=data[i+1]
            else : #나눗셈
                if tot<0:
                    tot=-((-tot)//data[i+1])
                else : 
                    tot//=data[i+1]

        if tot<mini:
            mini=tot
        if tot>maxi:
            maxi=tot

    else :
        for i in range(4):#연산자의 갯수만큼(op의 인덱스 0 1 2 3 검사해야함)
            if op[i]>0:#연산자가 존재한다면
                res.append(i) #연산자 인덱스를 res에 저장 0 1 2 3 / 덧 뺄 곱 나
                op[i]-=1
                perm(N+1)
                res.pop()
                op[i]+=1
            
if __name__=="__main__":
    datat=0
    mini=1000000000
    maxi=-1000000000
    n=int(input())
    data=list(map(int,sys.stdin.readline().split()))
    op=list((map(int,sys.stdin.readline().split())))#무조건 n-1개 연산자가 주어짐)
    chk=[0]*(n)
    res=[]
    perm(0)
    print(maxi)
    print(mini)

<반성 점>

<배운 점>

• global 전역변수를 적절하게 사용하자