[백준] 14888번 연산자 끼워넣기

사용 언어 - Python3

14888번: 연산자 끼워넣기 (실버1, DFS 백트래킹 문제)

문제 ★백트래킹 문제, 삼성 SW 역량 테스트 기출 문제★

14888번: 연산자 끼워넣기

 

 

정답

DFS 백트래킹 재귀함수 조합 문제 !!

다른 분들 답중에 가장 좋다고 생각하는 풀이법으로 공부했습니다. 맨 아래에 링크를 올립니다!

 

1.  maximum, minimum 지정

결과값을 출력할 때 결과값은 항상 -10억보다 크거나 같고, 10억보다 작거나 같은 결과로 나와야 한다.

그렇기 때문에 1e9, -1e9로 선언해준다.

maximum = -1e9 = -1*109 = -1000000000 (-10억 보다 크거나 같아야 한다)

minimum = 1e9 = 1*109 = 1000000000 (10억보다 작거나 같아야 한다)

 

2. back() 백트래킹 사용

연산은 N까지 진행한다. depth 인자를 활용하여 한번 연산을 할 때마다  depth+1을 해주어 depth가 4일 때 출력값을 뽑고 종료하도록 return한다.

현재까지 저장된 maximum, minimum 값과 새롭게 구한 total 값 중 최대, 최소값을 구하여 출력하면 정답이다.

 

plus, minus, multiple, divide가 있는 경우,

현재의 값(total)에서 해당하는 값을(num[depth]) 더해주거나 빼주거나 곱해주거나 나눠준다.

한 번 연산을 했기 때문에 depth를 +1 하고, 각각의 횟수를 한 개씩 빼준 상태로 back 재귀함수를 진행한다.

 

# 정답
N = int(input())
num = list(map(int,input().split()))
op = list(map(int,input().split()))

maximum = -1e9
minimum = 1e9

def back(depth,total,plus,minus,multiple,divide):
    global maximum, minimum
    
    if depth == N:
        maximum = max(maximum,total)
        minimum = min(minimum,total)
        return
    
    if plus:
        back(depth+1,total+num[depth],plus-1,minus,multiple,divide)
    if minus:
        back(depth+1,total-num[depth],plus,minus-1,multiple,divide)
    if multiple:
        back(depth+1,total*num[depth],plus,minus,multiple-1,divide)
    if divide:
        back(depth+1,int(total/num[depth]),plus,minus,multiple,divide-1)

back(1,num[0],op[0],op[1],op[2],op[3])
print(maximum)
print(minimum)

 

 

 

---

레퍼런스

• 정답 참고

[BOJ 14888] 연산자 끼워넣기 (Python)

•  1e9, -1e9

[파이썬 개념] 1e9

• 깃허브 정답

GitHub - yyeongeun/codingtest: 코딩테스트 공부