백준 21943번 연산 최대로 (c++)

상당히 복잡해보이지만 고민할 필요 없다

순서도 내마음대로, 연산자는 정해진 갯수 내에서 마음대로 배치하라는 뜻은

괄호따윈 의미 없다는 뜻이다.

연산자 우선순위가 없고 덧셈과 곱셈만 있다는것은

덧셈으로 이루어진 덩어리들을 곱해서 최대의 수를 만들라는것과 같은말이다.

 

완전탐색으로 수열의 어느 부분을 끊어서 나눌지 만들고

곱셈의 갯수+1 만큼의 덩어리가 만들어지면

수열을 순열로 만들어 모든 배치를 만들어 한번씩 계산해보아 최대값을 구한다.

 

void sol(int idx, vector<int> cut)
{
	if (cut.size() == q)
	{
		calc(cut);
		return;
	}

	for (int i = idx; i < n; i++)
	{
		cut.push_back(i);
		sol(i + 1, cut);
		cut.pop_back();
	}
}

덩어리를 만든다.

n 길이의 수열을 어느부분에서 자를지 결정한다.

 

void calc(vector<int> cut)
{
	cut.push_back(n);
	vector<int> tmp = arr;
	sort(tmp.begin(), tmp.end());
	do
	{
		ll result = 1;
		int old = 0;
		for (int i = 0; i < cut.size(); i++)
		{
			ll save = 0;
			for (int j = old; j < cut[i]; j++)
			{
				save += tmp[j];
			}
			old = cut[i];
			result *= save;
		}
		ans = max(ans, result);
	} while (next_permutation(tmp.begin(), tmp.end()));
}

다 잘랐으면 계산한다.

주어진 수열을 순열계산으로 모든 경우의수를 전부 따져본다.

 

signed main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	cin >> n;
	for (int i = 0; i < n; i++)
	{
		int a;
		cin >> a;
		arr.push_back(a);
	}
	cin >> p >> q;
	if (q == 0)
	{
		for (auto a : arr) ans += a;
		cout << ans << endl;
		return 0;
	}
	vector<int> tmp;
	sol(1, tmp);
	cout << ans << endl;

}

곱셈이 0인 경우는 모든 수를 더해주기만 하면 되기 때문에 바로 계산 후 답을 출력한다.

 

 

단순하게 생각하는 법을 익히자