연산자 끼워넣기 (feat. 백준, 14888번)

연산자 끼워넣기
https://www.acmicpc.net/problem/14888

14888번: 연산자 끼워넣기

반응형

// woohyeon.kim
// https://www.acmicpc.net/problem/14888
#include <iostream>
using namespace std;
int N, arr[11], sign[10], tmp[10], min_ans, max_ans;
bool chk[10];
void dfs(register int count) {
	if (count == (N - 1)) {
		register int ans = arr[0];
		for (register int i = 1; i < N; ++i) {
			if (tmp[i - 1] == 1)		ans += arr[i];
			else if (tmp[i - 1] == 2)	ans -= arr[i];
			else if (tmp[i - 1] == 3)	ans *= arr[i];
			else						ans /= arr[i];
		}
		min_ans = min(min_ans, ans), max_ans = max(max_ans, ans);
		return;
	}
	for(register int i = 0; i < N - 1; ++i)
		if (!chk[i]) {
			chk[i] = true;
			tmp[count] = sign[i];
			dfs(count + 1);
			chk[i] = false;
			tmp[count] = 0;
		}
}
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
	cin >> N;
	for (register int i = 0; i < N; ++i)
		cin >> arr[i], chk[i] = false;
	for (register int i = 0, v, idx = 0; i < 4; ++i) {
		cin >> v;
		while (v--)
			sign[idx++] = i + 1;
	}
	min_ans = static_cast<int>(1e9), max_ans = -static_cast<int>(1e9);
	dfs(0);
	cout << max_ans << "\n" << min_ans;
	return 0;
}
// *&)*@*

연산자에 대해서 모든 순열을 구하고, 각각의 순열대로 연산 후 최소값, 최대값을 구하는 방식입니다.

단, 최대값은 초기 0으로 하면 연산자가 하나만 있고 음수인 경우, 항상 0으로만 출력되기 때문에 조심해야 합니다.