연산자 배치하기(2017 하반기 오후 2번, 백준 14888 연산자 끼워넣기)

문제 링크: https://www.codetree.ai/frequent-problems/arrange-operator/description

코드트리

*같은 문제: 백준 14888 - 연산자 끼워넣기

 

백준의 경우 코드트리 문제에서 연산자 종류에 나눗셈이 추가되었다. 뭐... 그렇다고 문제가 크게 복잡해지지는 않는다. 

 

가능한 모든 경우의 수를 다 체크해보고 정답을 출력하면 된다. 매 상황에서 추가할 수 있는 연산자를 사용하고 다음 상황으로 재귀적으로 넘어가도록 코드를 짰다.

 

참고로, x라는 리스트가 있을 때, y=x 하면 얕은 복사가 이루어진다. deepcopy를 쓰거나 y=x[:]와 같이 쓰자.

 

백준이나 코드트리에는 백트래킹으로 분류해뒀는데, 뭐 맞나...?

 

	def dfs(order, num_oper):
	global max_val, min_val
	tmp = num_oper
	if num_oper[0] > 0: # 덧셈 가능
	tmp[0] -= 1
	dfs(order+[0], tmp)
	tmp[0] += 1
	if num_oper[1] > 0: # 뺄셈 가능
	tmp[1] -= 1
	dfs(order+[1], tmp)
	tmp[1] += 1
	if num_oper[2] > 0: # 곱셈 가능
	tmp[2] -= 1
	dfs(order+[2], tmp)
	tmp[2] += 1
	if sum(num_oper) == 0: # 연산자 모두 사용함
	val = lst[0]
	for i in range(n-1):
	if order[i] == 0: # 덧셈
	val += lst[i+1]
	elif order[i] == 1: # 뺄셈
	val -= lst[i+1]
	elif order[i] == 2: # 곱셈
	val *= lst[i+1]
	max_val = max(max_val, val)
	min_val = min(min_val, val)
	return
	if __name__ == "__main__":
	n = int(input())
	lst = list(map(int, input().split()))
	num_oper = list(map(int, input().split()))
	max_val, min_val = -10**10, 10**10
	dfs([], num_oper)
	print(min_val, max_val)

view raw 연산자 배치하기.py hosted with ❤ by GitHub