14888 연산자 끼워넣기

문제링크

코드 설명

N과 M 시리즈 문제로 백트래킹 복습을 한번 한 이후라 쉽게 풀수있었다.
연산자를 각각 math배열에 넣어둔후 dfs와sum을이용하여 값을 구했다.

소스 코드

#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
int N;
int arr[11];
int math[4];
int vect[10];
vector<int> result;
int sum;
void dfs(int level, int now) {
	if (level == N-1) {
		//연산 기록
		int a = 0;
		sum = arr[a];
		for (int i = 0; i < N-1; i++) {
			if (vect[i] == 1) { //더하기
				sum+= arr[a + 1];
			}
			else if (vect[i] == 2) { //뺴기
				sum-= arr[a + 1];
			}
			else if (vect[i] == 3) { //곱
				sum *= arr[a + 1];
			}
			else if(vect[i] == 4){ //나누기
				sum /= arr[a + 1];
			}
			else {
				continue;
			}
			a++;
		}
		result.push_back(sum);
		return;
	}
	for (int i = 0; i < 4; i++) { //연산 백트래킹
		if (math[i] <= 0) continue;
		else {
			vect[level] = i + 1; //1)덧셈 2) 뺼샘 3) 곱셈 4) 나눗셈
		}
		math[i]--;
		dfs(level + 1, i);
		math[i]++;
	}


}


int main() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> arr[i];
	}
	for (int i = 0; i < 4; i++) {
		cin >> math[i];
	}
	dfs(0, 0);
	sort(result.begin(), result.end());
	cout << result[result.size() - 1] << endl << result[0];

	return 0;
}