[C++] 백준 22945번: 팀 빌딩

문제 링크

22945번: 팀 빌딩

문제 요약

개발자 두 명이 팀을 이뤄야 하는데, 이 팀의 능력치는
(개발자 A와 개발자 B 사이에 존재하는 다른 개발자 수) × min(개발자 A의 능력치, 개발자 B의 능력치)
를 통해서 구할 수 있다. 구성할 수 있는 팀의 최대 능력치를 구해야 한다.

접근 방법

일단 최초 상태에서는 양 끝의 개발자를 후보로 둡니다. 두 개발자의 스탯 최솟값과, 두 개발자 사이의 사람 수가 곱해질 것이기 때문에 가능한 한 크게 잡았습니다.

1 2 3 4 5

이와 같은 예시에서는 양 끝을 후보로 잡습니다. 이때의 능력치는 $min(1, 5) \times 3 = 3$입니다. 그런데 두 후보 중에 작은 쪽의 후보를 한 칸 옆의 후보로 이동시키면 능력치가 증가할 수 있습니다. 피승수는 1 감소하지만, 승수의 증가에 따라 곱이 더 커질 수 있기 때문입니다. 위의 예시에서 1 대신 2를 선택하면 $min(2, 5) \times 2 = 4$가 됩니다.

따라서 두 포인터를 이용해서, 양 끝에서부터 더 작은 수를 가리키는 포인터를 가운데를 향해 이동시키는 방식으로 구현을 했습니다.

코드

#include <bits/stdc++.h>

using namespace std;

int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int n;
	cin >> n;
	
	vector<int> v(n);
	for (int i = 0; i < n; i++)
		cin >> v[i];

	int s = 0, e = n - 1, ans = 0;
	while (s <= e)
	{
		int between = e - s - 1;
		ans = max(ans, between * min(v[s], v[e]));

		if (v[e] > v[s])
			s++;
		else
			e--;
	}

	cout << ans << '\n';
	return 0;
}