백준 14888. 연산자 끼워넣기

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

14888번: 연산자 끼워넣기

삼성 SW 역량 테스트 기출문제라 해서 설레는 마음으로 풀어본 문제 !

 

생각보다 까다로웠던 부분이 있었다. 첫째로 C++14 버전 음수 나누기를 따라서, 결과가 (양수 값 // 분모) * -1 식으로 나와야 한다는 점.

파이썬으로 실험해본 결과 그냥 (음수 // -분모) * -1 로 처리하는 것 같은데, 어쨌든 달라서 다시 계산해줘야 했다.

둘째로 연산자를 백트래킹으로 식에 넣는 게 생각보다 까다로웠다. 처음 했던 생각은 연산자를 숫자로 구별하여 마지막 식에서 합치는 방법이었는데, 이리저리 처리하기도 귀찮고 해서 연산자 문자열 그대로 처리하는 방법을 고안했다.

 

기본적인 아이디어는 다음과 같다. 

우선 개념적으로 리스트 세 개가 쓰인다. 하나는 처리할 숫자 리스트, 처리할 연산자 리스트, 연산자의 개수 리스트(n-1개).

깊이우선탐색 한 싸이클 당 연산자 하나를 처리할 연산자 리스트에 넣고, 연산자의 개수 리스트에서 해당 연산자의 개수를 하나 빼 준 뒤, 다음 자리에 올 연산자로 넘어가면 된다.

이런 방식으로 dfs를 반복하면 +-*/ 인 사칙연산에 대해 [1,0,1,0] 의 개수 리스트는

[+, *] 과 [*, +] 두 가지 경우를 가지게 되어 모두 탐색하게 된다.

첫 싸이클 :

처리할 연산자 = ['+', 0], 연산자 개수 [0,0,1,0] -> dfs로 뒷자리 탐색.

두 번째 싸이클 :

*가 1개 있으므로 해당 인덱스에서 진행. 첫자리 ['*', 0]이 되고 dfs로 뒷자리 탐색.

 

이러한 방식이 가능하다.

 

n = int(input())

arr = list(map(int, input().split()))
ops_count = list(map(int, input().split()))

mn = 10**9
mx = -1*(10**9)
ops = ['+', '-', '*', '//']
ops_eval = [0] * (n - 1)

def calculate(arr, ops_eval):
	arr_idx = 0
	res = arr[0]
	op = 0
	for i in range(len(ops_eval)):
		if res < 0 and ops_eval[i] == '//':
			res = ((res * -1) // arr[i + 1]) * -1
			continue
		res =  eval(str(res) + ops_eval[i] + str(arr[i + 1]))
	return res

def dfs(col):
	global ops_count, ops, ops_eval, mx, mn
	if col == n - 1:
		val = calculate(arr, ops_eval)
		if val > mx:
			mx = val
		if val < mn:
			mn = val
		return
	for i in range(4):
		if ops_count[i] != 0:
			ops_eval[col] = ops[i]
			ops_count[i] -= 1
			dfs(col + 1)
			ops_count[i] += 1
dfs(0)
print(mx)
print(mn)

주의할 점으로는 최소 최대값이 -10억 ~ 10억이기 때문에 해당 값으로 범위를 설정해주자.