14888: 연산자 끼워넣기

난 아직도 내가 작성한 코드가 왜 틀리는 지를 모르겠다/ 그래도 일단 기록은 해둠
-> 해결완/ 1e9, -1e9 설정할 때 저게 float 타입이라 int(1e9), int(-1e9) 해줘야함

import sys

def dfs(depth, result, op1, op2, op3, op4):
	global max_result
	global min_result

	if depth == N:
		max_result = max(max_result, result)
		min_result = min(min_result, result)
		return

	if op1:
		dfs(depth + 1, result + A[depth], op1 - 1, op2, op3, op4)
	if op2:
		dfs(depth + 1, result - A[depth], op1, op2 - 1, op3, op4)
	if op3:
		dfs(depth + 1, result * A[depth], op1, op2, op3 - 1, op4)
	if op4:
		dfs(depth + 1, int(result / A[depth]), op1, op2, op3, op4 - 1)
	
N = int(input())
A = list(map(int, input().split()))
operator = list(map(int, input().split())) #+, -, x, /

max_result = int(-1e9)
min_result = int(1e9)
dfs(1, A[0], operator[0], operator[1], operator[2], operator[3])
print(max_result)
print(min_result)

• dfs와 백트래킹의 차이: dfs는 완전 탐색을 기본으로 하는 그래프 순회 기법으로 가능한 모든 경로는 탐색함. 백트래킹은 경로는 찾는 도중에 해가 되지 않을 것 같은 경로가 있다면 더 가지 않고 되돌아옴
• 이 문제는 백트래킹을 이용해서 탐색해야함
• operator 리스트에서 dfs하기 전에 -1하고 dfs 후에 +1 해주는 방식으로 구현할 수도 있지만, 나는 그냥 dfs 함수 인자로 operator의 값들을 넘겨주었음
• 모든 operator를 사용한 경우 (depth == N인 경우) max_result와 min_result를 갱신해주고 return