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

분류 

dfs

요구사항

주어진 연산자와 숫자를 사용해서 최대 값과 최소 값 구하기

풀이

숫자는 고정되어 있으니, 연산자의 순서만 고려하면 된다

주어진 숫자대로 연산자를 사용할 수 있다.

조건이 만족할때 연산자를 사용 -> 다음 이동 식으로 풀이하면 된다

 

ㄹ

#include <iostream>
#include <queue>
#include <algorithm>
#include <string.h>
#include <vector>
#include <string>
using namespace std;
//&:0 *:1 [] :2
int n;
int map[14];
int a, b, c, d;
long long Mans = -987654321;
long long mans = 987654321;
// 플 마 곱 나
void solve(int x, int y, int w, int z, long long sum,int cnt) {
	if (x + y + w + z == a + b + c + d) {
		Mans = max(Mans, sum);
		mans = min(mans, sum);
		return;
	}
	if (x < a) {
		solve(x+1,y,w,z,sum+map[cnt],cnt+1);
	}
	if (y < b) {
		solve(x, y+1, w, z, sum - map[cnt], cnt + 1);
	}
	if (w < c) {
		solve(x, y, w+1, z, sum * map[cnt], cnt + 1);
	}
	if (z < d) {
		solve(x, y, w, z+1, sum / map[cnt], cnt + 1);
	}
}
int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &map[i]);
	}
	scanf("%d%d%d%d", &a, &b, &c, &d);
	solve(0, 0, 0, 0, map[0],1);
	cout << Mans << endl;
	cout << mans << endl;
}