[Algo Rhythm🕺💃]BOJ 14888 - 연산자 끼워넣기

문제 분석

$N (2 \le N \le 11)$개의 수로 이루어진 수열 $A_1, A_2, A_3, ..., A_n$의 순서는 바꿀 수 없지만 숫자 사이 들어가는 연산자들의 순서는 바꿀 수 있다. 따라서 이 문제는 연산자들의 순서에 대한 '모든 조합을 구한 뒤' 계산한 결과들 중 최대값과 최소값을 구하는 문제로 이해할 수 있다.

 

문제 풀이

1. 최적화 🙅‍♂️

연산자들의 순서에 대한 모든 조합을 구하기 위해 backtracking을 사용했다.

이때 방문해야 하는 vertex들은 연산자들인데 연산자들의 종류를 구분하기 위해 enum을 정의했다. 또한 연산자들의 개수는 입력에 따라 가변적이기 때문에 정의한 enum을 저장하는 vector를 정의했다.

backtracking에 사용한 점화식은 아래와 같다. 이때 $acc, n\_idx, n, a, ops$는 각각 누적 계산값, 계산에 사용할 수열의 인덱스값, 수열의 길이, 수열을 저장한 배열, 연산자들을 저장한 vector이다.

$f(acc, n\_idx, n)= \begin{cases} get\ max/min & if\ n\_idx == n\\ for(op : ops)\ f(acc\ op\ a[n\_idx], n\_idx, n)& else\ if\ op\ not\ visited\end{cases}$

 

2. 최적화 🙆‍♂️

생각해보니 앞서 사용한 vector를 굳이 사용할 필요가 없었다. 이를 제외하여 재귀함수로 최적화했다.

이때 사용한 점화식은 아래와 같다. $acc, n_\_idx, n, a, n\_add, n\_sub, n\_mul, n\_div$는 각각 누적 계산값, 계산에 사용할 수열의 인덱스값, 수열의 길이, 수열을 저장한 배열, add 연산자의 개수, sub 연산자의 개수, mul 연산자의 개수, div 연산자의 개수를 의미이다.

$f(acc, n\_idx,n\_add, n\_sub, n\_mul, n\_div)= \begin{cases} get\ max/min & if\ n\_idx == n\\ f(acc + a[n\_idx], n\_idx + 1, n\_add - 1, n\_sub, n\_mul, n\_div) & else\ if\ n\_add\ != 0\\f(acc + a[n\_idx], n\_idx + 1, n\_add, n\_sub - 1, n\_mul, n\_div) & else\ if\ n\_sub\ != 0\\f(acc + a[n\_idx], n\_idx + 1, n\_add, n\_sub, n\_mul - 1, n\_div) & else\ if\ n\_mul\ != 0\\f(acc + a[n\_idx], n\_idx + 1, n\_add, n\_sub, n\_mul, n\_div - 1) & else\ if\ n\_div\ != 0\\ \end{cases}$

 

복잡도 분석

$n (2 \le n \le 11)$개의 수가 주어질 때, 시간 복잡도와 공간 복잡도는 아래와 같다.

1. 최적화 🙅‍♂️

• 시간 복잡도 : $O(n^2)$
  • n - 1번의 recursive call이 있고 각 recursive call마다 n - 1개의 연산자들이 담긴 vector를 순회하기 때문에
• 공간 복잡도 : $O(n)$
  • n - 1개의 연산자를 저장하는 vector, n개의 수열을 저장하는 배열이 있기 때문에

2. 최적화 🙆‍♂️

• 시간 복잡도 : $O(n^2)$
  • n - 1번의 recursive call이 있고 i번째 recursive call마다 (n - 1 - i)번의 recursive call이 있기 때문에
• 공간 복잡도 : $O(n)$
  • n개의 수열을 저장하는 배열이 있기 때문에

코드

1. 최적화 🙅‍♂️

 

2. 최적화 🙆‍♂️

 

문제 출처

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

14888번: 연산자 끼워넣기