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

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

14888번: 연산자 끼워넣기

# 삼성SW 역량테스트 기출문제이다. (백트래킹)

 

1. N과 숫자들 A를 입력받고 덧셈, 뺄셈, 곱셈, 나눗셈의 연산 갯수도 입력받는다.

 

2. BT(add, sub, mul, div, A[0], 1)을 실행한 뒤, max(answer)와 min(answer)를 출력한다.

 

# BT함수: 

      a. 종료조건: 모든 연산갯수가 0이라면 answer에 res를 넣어주고 함수를 종료한다.

 

      b. 재귀호출: 만약 add연산이 1이상이라면 add개수를 1줄이고 나머지 연산갯수는 그대로이므로

                         그대로 넘겨주고, res에 A[i]를 더한 값, 다음 인덱스를 가리키는 i+1을 넘겨준다.

 

                     만약 sub연산이 1이상이라면 sub개수를 1줄이고 나머지 연산갯수는 그대로이므로

                         그대로 넘겨주고, res에 A[i]를 뺀 값, 다음 인덱스를 가리키는 i+1을 넘겨준다.

 

                     만약 mul연산이 1이상이라면 mul개수를 1줄이고 나머지 연산갯수는 그대로이므로

                         그대로 넘겨주고, res에 A[i]를 곱한 값, 다음 인덱스를 가리키는 i+1을 넘겨준다.

 

                     만약 div연산이 1이상이라면 div개수를 1줄이고 나머지 연산갯수는 그대로이므로

                         그대로 넘겨주고, res를 A[i]로 나눈 값, 다음 인덱스를 가리키는 i+1을 넘겨준다.

                         (나누는 과정에서 res가 0보다 작으면 양수로 바꾼뒤 A[i]로 나누고 다시 음수로 바꿔야

                           하므로 if문으로 나눠서 처리했다.)

 

import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int,input().split()))
add, sub, mul, div = map(int,input().split())
answer = []
def BT(add, sub, mul, div, res, i):
	# 종료 조건
	if add == 0 and sub == 0 and mul == 0 and div == 0:
		answer.append(res)
		return
	
	# 재귀 호출
	if add:
		BT(add - 1, sub, mul, div, res + A[i], i+1)
	if sub:
		BT(add, sub - 1, mul, div, res - A[i], i+1)
	if mul:
		BT(add, sub, mul - 1, div, res * A[i], i+1)
	if div:
		if res < 0:
			BT(add, sub, mul, div - 1, -(-res // A[i]), i+1)
		else:
			BT(add, sub, mul, div - 1, res // A[i], i+1)

BT(add, sub, mul, div, A[0], 1)
print(max(answer))
print(min(answer))

(solved.ac 티어: 실버 1)