[코딩테스트][백준] 🔥 백준 14888번 "연산자 끼워넣기" 문제: Python으로 완벽 해결하기! 🔥

김상욱·2024년 7월 30일
0
post-thumbnail

문제 링크

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

🕒 Python 풀이시간: 20분

n=int(input())
arr=list(map(int,input().split()))
oper=list(map(int,input().split()))

def custom_division(a, b):
    if a>0:
        return a//b
    else:
        a=-a
        return -(a//b)

def dfs(n,arr,oper,depth,result):
    global max_value,min_value
    if depth==n-1:
        max_value=max(max_value,result)
        min_value=min(min_value,result)
        return
    if oper[0]>0:
        oper[0]-=1
        dfs(n,arr,oper,depth+1,result+arr[depth+1])
        oper[0]+=1
    if oper[1]>0:
        oper[1]-=1
        dfs(n,arr,oper,depth+1,result-arr[depth+1])
        oper[1]+=1
    if oper[2]>0:
        oper[2]-=1
        dfs(n,arr,oper,depth+1,result*arr[depth+1])
        oper[2]+=1
    if oper[3]>0:
        oper[3]-=1
        dfs(n,arr,oper,depth+1,custom_division(result,arr[depth+1]))
        oper[3]+=1

result=arr[0]
max_value=-int(1e9)
min_value=int(1e9)
dfs(n,arr,oper,0,result)
print(max_value)
print(min_value)

🔍📈📉 백트래킹을 통한 최댓값과 최솟값 탐색

숫자와 연산자의 갯수가 10개 정도이기 때문에 모든 경우의 수를 구하며 탐색하는 백트래킹을 생각할 수 있다. 이 때, 연산의 결과도 최대 값이 10억 이하 -10억이 나올 수 있기 때문에 최대 최솟값도 10억을 기준으로 맞추어놓아야 제대로 된 정답을 도출할 수 있다.

각 연산자를 부여하면서 해당 결과값을 남은 연산자가 없을 때까지 수행하고 깊이를 깊게하면 된다. 그러다가 원하는 만큼의 깊이, 즉 모든 연산자가 소진되고 숫자가 계산되었을 때를 기준으로 값을 기준으로 최대, 최소값을 갱신하면 된다.

나누기 연산의 경우, 이 문제의 한하여 음수의 연산을 따로 다루고 있기 때문에 이 점에 유의하여 풀면된다.

이렇게 Python으로 백준의 "연산자 끼워넣기" 문제를 해결해보았습니다. 코드와 개념 설명을 참고하여 문제를 해결하는 데 도움이 되셨길 바랍니다! 😊

0개의 댓글