[백준] 14888 연산자 끼워넣기

백준14888링크

문제

• N개의 수로 이루어진 수열 A1, A2, ..., AN과 N-1개의 연산자(덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷))
• 식의 계산은 연산자 우선 순위를 무시하고 앞에서부터 진행
• 만들 수 있는 식의 결과가 최대인 것과 최소

입력

첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어짐
둘째 줄에는 A1, A2, ..., AN
셋째 줄에는 합이 N-1인 4개의 정수 (차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱셈(×)의 개수, 나눗셈(÷))

출력

첫째 줄에 만들 수 있는 식의 결과의 최댓값을, 둘째 줄에는 최솟값을 출력
식의 결과는 항상 -10억보다 크거나 같고, 10억보다 작거나 같다.

풀이

수열을 앞에서부터 순서대로 진행하면서 넣을 수 있는 연산자의 모든 조합을 알아봐야함.
-> DFS로 풀이

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>

using namespace std;

int N;
int oper[4] = { 0, }; //연산자 개수 저장
vector<int> nums; //수열 저장

int rmin = 1000000001; //최소값
int rmax = -1000000001; //최대값

void cal(int index, int result) {
	if (index >= N) {
		if (rmin > result) {
			rmin = result; //최소값 갱신
		}
		if (rmax < result) {
			rmax = result; //최대값 갱신
		}
		return;
	}

	for (int i = 0; i < 4; i++) {
		if (oper[i] > 0) {
			oper[i]--; //연산자가 존재하는 경우 -1
			if (i == 0) { //더하기인 경우
				cal(index+1, result+nums[index]);
			}
			else if (i == 1) { //빼기인 경우
				cal(index + 1, result-nums[index]);
			}
			else if (i == 2) { //곱하기인 경우
				cal(index + 1, result * nums[index]);
			}
			else { //나누기인 경우
				cal(index + 1, result / nums[index]);
			}
			oper[i]++; //탐색 종료 후 +1 (원상복귀)
		}
	}
	return;

}

int main() {
	
	cin >> N;

	int temp;
	for (int i = 0; i < N; i++) {
		cin >> temp;
		nums.push_back(temp);
	}

	for (int i = 0; i < 4; i++) {
		cin >> temp;
		oper[i] = temp;
	}

	cal(1, nums[0]); //첫번째값 넣은 후 탐색 시작

	cout << rmax << "\n";
	cout << rmin << "\n";
	return 0;
}