[백준 #14888] 연산자 끼워넣기 - 파이썬(python)

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

삼성 SW 역량 테스트 기출문제라고 해서 굉장히 겁을 먹었다.

역시 머릿속에 있는것을 구현하는게 쉽지않았는데,

일단 차근차근 했다.

from itertools import permutations
N=int(input())
numlist=list(map(int,input().split()))
calcnt=list(map(int,input().split()))
callist=[]
for i in range(4):
    if calcnt[i]==0: continue
    else: 
        for j in range(calcnt[i]):
            callist.append(i)
calcombi=list(permutations(callist,len(callist)))

def calchoice(a,tmp,elem):
    if a==0:
        return tmp+elem
    elif a==1:
        return tmp-elem
    elif a==2:
        return tmp*elem
    else: 
        if tmp<0:
            return -((-tmp)//elem)
        else: return tmp//elem

def calculate(arr,sym):
    result=[]
    for i in range(len(sym)):
        temp=arr[0]
        for j in range(N-1):
            temp=calchoice(sym[i][j],temp,arr[j+1])
        result.append(temp)
    return result

calresult=calculate(numlist,calcombi)
print(max(calresult))
print(min(calresult))

내가 푼 방법은 사실,, 백트래킹과 관련이 매우 없어보인다.

입력받은 연산자의 종류와 수로 순열을 만들어서,

모든 조합에 대입해서 나온 값 중 최댓값과 최솟값을 찾는 것으로 풀이했다.

(이런 풀이는 브루트포스...)

 

백트래킹 문제라는걸 까먹고 일단 코딩을 하는데에만 집중한 것 같다..

 

그래서 여러 코딩을 참고해서 다시 한 번 코딩을 짰다.

(이해하지도 못한 코딩 복붙은 지양해야지)

 

<수정 한 부분>

 

1.

입력받은 연산자의 개수를 리스트로 펼칠 때 for문을 이용하지 않고

직관적으로 갯수만큼 곱해서 만들었다.

2.

순열의 중복을 없앰

(같은 연산자가 같은 순서로 중복으로 등장할 수 있음)

3.

result 리스트로 모든 연산 결과를 받아서 return 하였는데,

결과값을 이전까지 산출한 최솟값, 최댓값과 비교하여서 더 작거나 큰 경우에만 값을 저장하여 return 하였다.

3-1.

연산을 하다가 최솟값보다 커지거나, 최댓값보다 작아지는 경우에는 나머지 연산을 하지 않고 continue문으로 탈출시켜

다른 연산자 조합으로 넘어갈 수 있도록 함

 

from itertools import permutations
N=int(input())
numlist=list(map(int,input().split()))
plus,minus,multiple,division=list(map(int,input().split()))
callist=[]
callist+=[0]*plus
callist+=[1]*minus
callist+=[2]*multiple
callist+=[3]*division

calcombi=list(set(permutations(callist,N-1)))
def calchoice(a,tmp,elem):
    if a==0:
        return tmp+elem
    elif a==1:
        return tmp-elem
    elif a==2:
        return tmp*elem
    else: 
        if tmp<0:
            return -((-tmp)//elem)
        else: return tmp//elem

def calculate(arr,sym):
    less=10**9
    much=-(10**9)
    for i in sym:
        temp=arr[0]
        for j in range(N-1):
            temp=calchoice(i[j],temp,arr[j+1])
            if less<temp or much>temp:continue
        if less>temp:
            less=temp
        if much<temp:
            much=temp
    return (less,much)

calresult=calculate(numlist,calcombi)
print(calresult[1])
print(calresult[0])

좀 더 깔끔하지만 복잡한 코딩이 있었는데, 이해가 잘 가지 않았다.

복사&붙여넣기식으로 코딩 공부하는 것 보다 완전히 내 것으로 만드는게 중요하다고 생각하기때문에

나중에 다시 한 번 구현을 시도 해 봐야겠다.

아직 백트래킹, 재귀함수를 쓰는것이 어려운 것 같다.