백준 14888 연산자 끼워넣기

- N개의 수열과 N-1개의 연산자가 주어질 때, 가능한 모든 연산 결과의 최소값과 최대값을 구하는 문제이다.

 

- 브루트 포스 문제이고, N의 범위가 2 이상 11 이하인 것으로 보아, 재귀 백트래킹으로 풀 수 있는 문제임을 알 수 있다. (약 4^11 = 2^22)

 

- 백트래킹을 평소 열심히 연습해왔다면 쉽게 풀 수 있는 문제이다. 종결 조건은 cnt 매개변수가 n과 같아질 때, 즉 모든 피연산자를 사용 했을 때 최대 / 최소값을 최신화하면 된다.

 

#include <iostream>
#include <algorithm>
using namespace std;
int n;
int executed[11];
int num_plus, num_minus, num_multiply, num_divide;
int min_answer = 1000000000;
int max_answer = -1000000000;

void DFS(int cnt, int num_plus, int num_minus, int num_multiply, int num_divide, int total) {
	if (cnt == n) {
		min_answer = min(min_answer, total);
		max_answer = max(max_answer, total);
		return;
	}
	if (num_plus > 0) DFS(cnt + 1, num_plus-1, num_minus, num_multiply, num_divide,  total + executed[cnt]);
	if (num_minus > 0) DFS(cnt + 1, num_plus, num_minus-1, num_multiply, num_divide, total - executed[cnt]);
	if (num_multiply > 0) DFS(cnt + 1, num_plus, num_minus, num_multiply-1, num_divide, total * executed[cnt]);
	if (num_divide > 0) DFS(cnt + 1, num_plus, num_minus, num_multiply, num_divide-1, total / executed[cnt]);

}

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> executed[i];
	}
	cin >> num_plus >> num_minus >> num_multiply >> num_divide;
	DFS(1, num_plus, num_minus, num_multiply, num_divide, executed[0]);
	cout << max_answer << '\n';
	cout << min_answer << '\n';
    return 0;
}