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

분류

DFS/BFS 백트래킹 브루트포스 완전 탐색 등등... 풀이자에 따라 갈리는 듯

 

나의 아이디어 한줄정리

모든 경우의 수를 DFS를 통해 완전 탐색함. 모든 수를 탐색한 경우의 결과 값을 최대 최소 값과 비교한다.

 

코드

 

	from sys import stdin
	n = int(input())
	a = list(map(int, stdin.readline().split()))
	deli = list(map(int, stdin.readline().split()))
	# + - * // 의 순서로 매핑
	max_num = -1e9 - 1
	min_num = 1e9 + 1
	def getDeli(i, val, next):
	if i == 0:
	return val + next
	elif i == 1:
	return val - next
	elif i == 2:
	return val * next
	elif i == 3:
	if val < 0:
	ret =(abs(val) // next)
	return -ret
	else:
	return val // next
	def DFS(idx, delis, val):
	global max_num
	global min_num
	if idx == n:
	max_num = max(max_num, val)
	min_num = min(min_num, val)
	else:
	for i, count in enumerate(delis):
	if count > 0:
	delis[i] -= 1
	DFS(idx + 1, delis, getDeli(i, val, a[idx]))
	delis[i] += 1
	DFS(1,deli,a[0])
	print(max_num)
	print(min_num)

view raw 14888.py hosted with ❤ by GitHub

 

각 연산자의 사용 가능 갯수와 연산자 기호를 매핑한 뒤

인덱스에 따른 연산을 getDeli(i, val, next) 를 통해 진행한다.

C++ 14 방식을 따르는 음수 // 양수 연산에 대해서는 따로 처리해보았다. 

// 로 단순하게 놓으면 테스트 3번에서 막히는 듯 하다.

사용한 count를 1- 해주고 DFS 연산을 한뒤 다시 돌아올 땐 다시 1+ 해주어야 한다.

가능한 값의 범위가 -10억 ~ 10억 이므로 초기 값은 최소값 1e9+1, 최대값 -1e9-1로 설정했다.