[BOJ/C++] 22945 팀 빌딩

시간 복잡도

• N이 최대 100,000이기 때문에 $O(N^2)$ 시간복잡도의 알고리즘은 사용할 수 없습니다.

문제 접근법

• 정렬을 사용할 수 없고 A와 B의 사이의 개발자 수와 개발 능력이 바뀌어야 하기 때문에 양 끝에서 투 포인터를 이용하여 문제를 해결할 수 있습니다.
• 개발 능력이 더 작은 쪽의 포인터를 움직이는 방식으로 최댓값을 갱신합니다.

코드

#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <stack>
#include <deque>
#include <queue>
#include <string>
#include <climits>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>

using namespace std;

using int32 = long;
using int64 = long long;

static vector<int> v;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int N;
    cin >> N;

    v.resize(N);

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

    int l = 0, r = N-1, result=0;
    while(l<r)
    {
        result = max(result, (r - l - 1) * min(v[l], v[r]));

        if (v[l] < v[r])
            l++;
        else
            r--;
    }


    cout << result;

    return 0;
}