[BOJ] 22945번 팀 빌딩 (C++)

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

22945번: 팀 빌딩

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
	int n;
	cin >> n;
	vector<int> v;
	for(int i = 0; i < n; i++){
		int x;
		cin >> x;
		v.push_back(x);
	}
	
	int l = 0;
	int r = v.size() - 1;
	
	int max = 0;
	while(l < r){
		int a = (r - l - 1) * min(v[l], v[r]);
		if(a > max) max = a;
		
		if(v[l] < v[r]) l++;
		else r--;
	}
	cout << max << endl;
	return 0;
}

 

구간이 줄어들 때 A와 B 사이의 개발자 수는 무조건 줄게 되므로 l, r 포인터를 이동시킬 때 팀 능력치를 최대로 할 수 있도록 이동시켜야 한다. 현재 l, r 포인터 중 더 작은 것을 가리키고 있는 포인터를 이동시키면 팀 능력치의 손실을 줄일 수 있다.