[백준/Python] 연산자 끼워넣기

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

14888번: 연산자 끼워넣기

n = int(input()) # 수의 개수
nums = list(map(int, input().split())) # 숫자 리스트
op = list(map(int, input().split())) # 연산자 리스트
r_max, r_min = -1e9, 1e9 # 식의 최대값, 최소값

# DFS 수행
def dfs(depth, result, plus, minus, multiply, divide):
	global r_max, r_min
	if depth == n: # 더 이상 탐색할 숫자가 없는 경우
		r_max = max(r_max, result)
		r_min = min(r_min, result)
		return

    # 모든 경우 탐색
	if plus: 
		dfs(depth + 1, result + nums[depth], plus - 1, minus, multiply, divide)
	if minus:
		dfs(depth + 1, result - nums[depth], plus, minus - 1, multiply, divide)
	if multiply:
		dfs(depth + 1, result * nums[depth], plus, minus, multiply - 1, divide)
	if divide:
		dfs(depth + 1, int(result / nums[depth]), plus, minus, multiply, divide - 1)

dfs(1, nums[0], op[0], op[1], op[2], op[3])
print(r_max)
print(r_min)

이 문제는 백트래킹 문제로 DFS 를 사용하여 해결할 수 있었다.

1. 필요한 정보를 입력받는다.

2. DFS를 수행한다.

    2-1. 연산자 값이 0이 아니라면 모든 경우를 탐색한다.

    2-2. 더 이상 탐색할 숫자가 없는 경우 식의 최대값, 최소값을 구하고 재귀함수를 빠져나온다.

3. 식의 최대값, 최소값을 출력한다.

 

[ 주의할 사항 ]

처음에 틀렸다고 나와서 무엇이 문제인지 찾아보니 나누기할 때 연산자의 문제였다. 문제에서 나누기를 할 때 정수 나눗셈의 몫만 취한다고 되어있어서 // 연산자를 썼는데 이것 때문에 식의 결과값이 달라졌다. 그래서 / 연산자로 나눈 뒤 정수로 바꾸어 주는 것으로 바꾸었더니 해결되었다.

print( -1 / 3) # 출력 - -0.3333333333333333
print(int(-1 / 3)) # 출력 - 0
print(-1 // 3) # 출력 - -1