백준_14888_연산자 끼워넣기 (브루트포스-순열)

🌿문제: https://www.acmicpc.net/problem/14888

14888번: 연산자 끼워넣기

 

🌿알고리즘: 브루트포스 - 순열

이 문제를 저번에는 재귀로 풀었었는데, 이번에는 순열로 풀었다. 연산자의 개수가 N-1개로 정해져있고, 그들의 순서를 정하는 문제이기 때문에 순열로 풀 수 있다.

 

🌿algorithm 헤더의 minmax_element 함수를 사용하면 최대/최소값을 쉽게 구할 수 있다.

 

🌿코드:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int N;

int solve(vector<int> &a, vector<int> &op) {
	int result = a[0];
	int size = op.size();
	for (int i = 0; i < size; i++) {
		if (op[i] == 0) {
			result += a[i + 1];
		}
		else if (op[i] == 1) {
			result -= a[i + 1];
		}
		else if (op[i] == 2) {
			result *= a[i + 1];
		}
		else {
			result /= a[i + 1];
		}
	}
	return result;
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> N;
	vector<int> a(N);
	for (int i = 0; i < N; i++) {
		cin >> a[i];
	}
	vector<int> op;
	int x;
	for (int i = 0; i < 4; i++) {
		cin >> x;
		for (int j = 0; j < x; j++) {
			op.push_back(i);
		}
	}
	// 원래 다음 순열을 구하기 전에 정렬해야하지만 이 문제에서는 위에서 0,1,2,3 순으로 들어가므로 정렬 생략 가능
	vector<int> t;
	do {
		int tmp = solve(a, op);
		t.push_back(tmp);
	} while (next_permutation(op.begin(), op.end()));
	auto ans = minmax_element(t.begin(), t.end());
	cout << *ans.second << '\n';
	cout << *ans.first << '\n';
	return 0;
}