본문 바로가기
Algorithm/DFS&BFS&백트래킹&재귀

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

by HANNI하니 2023. 1. 19.

사용 언어 - Python3

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

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

 

14888번: 연산자 끼워넣기

첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 

www.acmicpc.net

 

 

정답

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)

링크위 문제를 보고 2가지 풀이 방법이 떠올랐다. 하나는 연산자들에 대한 순열을 구하여 푸는 방법이다. 다른 하나는 DFS를 이용해 최대, 최솟값을 구하는 방법이다. 순열은 파이썬 permutations 모

velog.io

'Algorithm > DFS&BFS&백트래킹&재귀' 카테고리의 다른 글

[백준] 10872번 팩토리얼  (0) 2023.01.23
[백준] 14889번 스타트와 링크  (1) 2023.01.20
[백준] 2580번 스도쿠  (0) 2023.01.19
[백준] 9663번 N-Queen  (0) 2023.01.19
[백준] 2339번 석판 자르기  (0) 2023.01.18

댓글