[BOJ/C++] 14888(연산자 끼워넣기)

Link

https://www.acmicpc.net/problem/14888

풀이 과정

• 전형적인 백트래킹의 느낌을 주는 문제여서 편하게 풀었습니다. 연산상의 실수만 없다면 아마 무난하게 풀 수 있는 문제라고 생각합니다.

1. 연산자 우선 순위 무시 -> 스택, 백트래킹, DP
2. 4개의 연산자를 갯수에 맞춰 연산 -> 백트래킹

정답 코드

#include<iostream>
using namespace std;

int n, maxVal = -1e9, minVal = 1e9;
int num[11];
int op[4];

void input() {
	cin >> n;
	for (int i = 0; i < n; ++i) {
		cin >> num[i];
	}
	for (int i = 0; i < 4; ++i) {
		cin >> op[i];
	}
}

void rec(int val, int idx, int plus, int minus, int mul, int div) {
	++idx;
	if (idx == n) {
		if (maxVal < val) maxVal= val;
		if (minVal > val) minVal = val;
		return;
	}
	if (plus > 0) rec(val + num[idx], idx, plus - 1, minus, mul, div);
	if (minus > 0) rec(val - num[idx], idx, plus, minus - 1, mul, div);
	if (mul > 0) rec(val * num[idx], idx, plus, minus, mul - 1, div);
	if (div > 0) rec(val / num[idx], idx, plus, minus, mul, div - 1);
}

void solution() {
	input();
	rec(num[0], 0, op[0], op[1], op[2], op[3]);
	cout << maxVal << '\n' << minVal;
}

int main() {
	cin.tie(0), cout.tie(0), ios_base::sync_with_stdio(0);
	solution();
	return 0;
}