(2024-11-02) 2 문제 : 백준 - 22945 (팀 빌딩)

 

두 개를 선택하는 모든 경우의 수를 고르기엔 N의 최대값이 100000이기 때문에 시간초과가 발생할 수 밖에 없다.

브루트포스를 제외하면 일차원 배열에서 두 개의 수를 선택하여 값을 구하는 문제는 보통 투포인터이기 때문에 투포인터로 접근해보았다.

 

투포인터를 양 끝에서부터 시작해서 안쪽으로 움직이게 한다면, 두 개발자의 능력치 최소값은 커질수도 있고 작아질수도 있지만 개발자 사이에 존재하는 다른 개발자의 수는 항상 작아진다. 즉 하나의 변수가 고정이된 것이다.

 

그러므로 먼저 양 끝에서부터 안쪽으로 투포인터가 이동하도록 하였다. 그렇다면 남은 것은 두 개발자의 능력치 최소치인데, 이 값은 그리디적으로 생각하였다. 현재 투 포인터가 가리키고 있는 두 개발자중 능력치가 더 낮은 쪽의 포인터가 안쪽으로 이동하도록 하였다.

 

#include <iostream>
#include <vector>
#include <climits>

void Init()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
}

int main()
{
    Init();

    int NumDeveloper = 0;
    std::cin >> NumDeveloper;

    std::vector<int> Stats(NumDeveloper);
    for (int i = 0; i < NumDeveloper; i++)
    {
        std::cin >> Stats[i];
    }

    int Left = 0;
    int Right = NumDeveloper - 1;
    
    int Answer = 0;

    while (Left <= Right)
    {
        int Dist = Right - Left - 1;
        Answer = std::max(Answer, Dist * std::min(Stats[Left], Stats[Right]));

        if (Stats[Left] < Stats[Right])
        {
            Left++;
        }
        else
        {
            Right--;
        }
    }

    std::cout << Answer;

    return 0;
}