[백준] 연산자 끼워넣기 (C++)

1. 문제

www.acmicpc.net/problem/14888

14888번: 연산자 끼워넣기

2. 풀이

재귀함수를 이용하여 해결

흔한 문제!! 숙지할 것 !!!

 

3. 코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

vector<int> v;
vector<int> oper(4, 0);  // +, -, x. %
int _max = -999999999;
int _min = 9999999999;
int N;

void dfs(int plus, int minus, int multi, int div, int idx, int total) {
	if (idx >= N) {
		if (total < _min)
			_min = total;
		if (total > _max) {
			_max = total;
		}
		return;
	}
	if (plus > 0) {
		dfs(plus-1, minus, multi, div, idx + 1, total + v[idx]);
	}
	if (minus > 0) {
		dfs(plus, minus - 1, multi, div, idx + 1, total - v[idx]);
	}
	if (multi > 0) {
		dfs(plus, minus, multi - 1, div, idx + 1, total*v[idx]);
	}
	if (div > 0) {
		dfs(plus, minus, multi, div - 1, idx + 1, total / v[idx]);
	}
	
}

int main() {

	freopen("input.txt", "r", stdin);

	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		int x;
		scanf("%d", &x);
		v.push_back(x);
	}
	for (int i = 0; i < 4; i++) {
		int x;
		scanf("%d", &x);
		oper[i] = x;
	}
	
	dfs(oper[0], oper[1], oper[2], oper[3], 1, v[0]);

	printf("%d\n", _max);
	printf("%d\n", _min);

	return 0;
}