[백준 14888번 / C++] 연산자 끼워넣기

완전탐색으로 dfs를 활용해서 풀면된다. 

 

+, -, * , /  연산자를 차례대로 넣어보는 것이다. 

 

예를 들어, 

1 3 5 라는 숫자가 주어졌고 각 연산자를 하나씩 대입해보자. 

 

1 + 3  = 4

1 - 3   = -2

1 * 3  = 3

1 / 3  = 0 

 

그리고 연산값이 4부터 다시 dfs를 호출해서 연산하면 된다. 

 

4 + 5 = 9

4 - 5 = -1

4 * 3 = 12

4 / 5  = 0

 

이후에 연산값이 -2 부터 다시 dfs 를 호출해서 연산한다. 

 

이렇게 dfs를 활용해서 완전탐색으로 풀면된다. 

#include <queue>
#include <iostream>
#include <algorithm>
using namespace std; 
#define INF 987654321; 
bool check[123456 * 2+1]; 
vector <int> v; 
int result_max = -INF; 
int result_min = INF; 
int level; 
void dfs(int plus, int minus, int multi, int divide, int result, int cnt) {
	if (plus < 0 || minus < 0 || multi < 0 || divide < 0)return; 
	if (cnt == v.size()) {
		result_max = max(result, result_max); 
		result_min = min(result, result_min); 
		return; 
	}
	dfs(plus - 1, minus, multi, divide, result + v[cnt], cnt+1); 
	dfs(plus , minus-1, multi, divide, result - v[cnt], cnt+1);
	dfs(plus , minus, multi-1, divide, result * v[cnt], cnt+1);
	dfs(plus , minus, multi, divide-1, result / v[cnt], cnt+1);	
}
int main() {	
	int n; cin >> n; 
	for (int i = 0; i < n; i++) {
		int a; cin >> a; 
		v.push_back(a); 
	}
	int a, b, c, d; 
	cin >> a >> b >> c >> d; 
	dfs(a,b,c,d, v[0], 1); 
	cout << result_max << endl; 
	cout << result_min << endl;

}

14888번: 연산자 끼워넣기