[Back Tracking] 연산자 끼워넣기 - 백준

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

14888번: 연산자 끼워넣기

 

백트래킹 문제는 보통 모든 경우를 시뮬레이션 하여 Brute force하게 문제를 풀어나가는 방법으로 접근을 시도.

퍼즐 문제를 푸는 유형들이 그러하였고 이 문제 역시 연산자들의 input 경우의 수가 많고 랜덤하기에 수많은 경우를 무식하게 때려박아 보는 방법으로 접근을 시도할 수 있다.

 

즉, 수많은 경우의 수를 가지고 문제를 풀어야 할 경우

Brute Force하게 접근을 해야하며 백트래킹 문제는 이를 Recursion을 활용하여 잘 구현을 해야한다.

 

또한 문제를 푸는 것만큼 중요한 게 이 문제가 바로 Back Tracking 유형인 지를 먼저 파악할 줄 아는 연습이 필요하다.

 

Solution

---

문제 풀이는 다음과 같이 접근을 시도.

 

주어진 숫자의 배열은 일정하고 연산자의 수는 (수의 갯수-1)만큼 이므로 연산자를 숫자들 사이에 랜덤하게 끼워 맞출 때 가장 값을 크게하는 경우와 작게 하는 경우를 찾는 알고리즘이다.

 

문제의 조건을 보면 숫자의 경우 2~11개 사이이고 수의 값은 1~100 이내의 값이다.

 

경우의 수를 보면

숫자가 N개 주어지고 연산자가 N-1개 주어진다고 하면

최악의 경우 N-1개를 N-1개 자리에 하나씩 넣어보는 시뮬레이션을 돌려야 하므로 (N-1)!의 경우의 수가 나오게 됨. 즉, O(n!)의 알고리즘이 나오므로 매우 경우의 수가 많은 문제라는 것을 파악.

→ 즉 이 문제는 백트래킹으로 브루트 포스하게 풀어야 함...!

 

우선 3번째 행은 각각 덧셈, 뺄셈, 곱셈, 나눗셈의 수를 나타내므로 이를 사용할 수 있는 연산자 형태로 바꾸어주었다.

예를 들어

[ 2, 0, 1, 2 ] 이렇게 주어진다고 하면

덧셈이 0, 뺄셈이 1, 곱셈이 2, 나눗셈이 3으로 labeling을 하면

[ 0, 0, 2, 3, 3 ] → 이렇게 갯수를 구해주어 새로운 연산자 배열 oper_list를 만들어준다.

 

이렇게 되면 연산자의 목록을 재정의하고 주어진 숫자 배열 num에서 랜덤하게 넣어보는 시뮬레이션을 구현하면 된다.

 

시뮬레이션은 다음과 같다.

다음 테스트 케이스를 생각해보자

이 경우 oper_list는 다음과 같이 정의되고

숫자 배열이 다음과 같이 정의가 되서 숫자들 사이에 연산자를 배치하는 과정을 거친다.

처음의 경우 맨 첫번째 연산자인 0(더하기)을 집어넣는다고 가정하면

다음과 같이 덧셈을 수행하고

덧셈을 수행한 결과는 새로운 first로 갱신이 된다.

oper_list 역시 처음 연산자 0을 사용하였으므로 그것을 제외한 나머지를 새로운 oper_list의 파라미터로 넘기게 된다. 여기서 재귀 함수를 시행해준다.

여기까지는 단순한 DFS 논리랑 비슷한데

중요한 점은 연산자 0이 처음 1과 2 사이에만 들어가라는 법이 없다.

즉 처음 연산자 0은 3이나 4 혹은 5나 6 사이에도 들어갈 수 있다.

이런 모든 경우의 수를 고려하기 위해

for 반복문을 통해 처음 0이 1과 2만이 아닌

3과 4 사이에도 들어가 recursion를 시작하는 방법을 통해 문제를 풀었다.

 

그렇게 하여 가장 Max, Min인 경우를 찾아주어 문제를 풀었다.

 

또한 문제에서 boundary를 -10억부터 10억까지 설정해주었으므로 Min, Max를 초기에 다음과 같이 설정해주었다.

 

문제 풀이 코드는 다음과 같다.

### input 처리
# 숫자의 갯수
N = int(input())
# 숫자 배열
num = [int(x) for x in input().split()]
# 연산자 수
oper = [int(x) for x in input().split()]

### 연산자의 리스트로 변환 과정 -- 숫자의 갯수를 n이라고 할 때 O(4(n-1))
oper_list = [i for i in range(len(oper)) for _ in range(oper[i])]

# 숫자 목록에서 다음 연산할 숫자를 가리키는 index
limit = 0

### 연산 수행 함수
def do_operate(first, second, op) : 
	if op == 0 : return first+second
	elif op == 1 : return first-second
	elif op == 2 : first*second
	else : 
		if first < 0 : 
			return (first*(-1))//second)*(-1)
		return first//second

### Do back tracking - O(n!) in worst case
def operate(first, second, op_list, limit, Max, Min) : 
	for idx range(len(op_list)) : 
		new = do_operate(first, second, op_list[idx])
		# 연산할 수가 2개밖에 없는 경우
		if limit == len(num)-2 : 
			return new, new
		if idx < len(op_list) -1 : 
			result = operate(new, num[limit+2], op_list[:idx]+op_list[idx+1:], limit+1, Max, Min)
		else : # 연산자가 마지막 한개 남은 경우
			result = operate(new, num[limit+2], op_list[:idx], limit+1, Max, Min)
		if Max < result[1] : 
			Max = result[1]
		if Min > result[0] : 
			Min = result[0]
	return Min, Max

mins, maxs = operate(num[limit], num[limit+1], oper_list, limit, -1000000000,1000000000)
print(maxs)
print(mins)

 

Time compleixty

---

최악의 경우 O(n!)이 아닐까 싶음