백준 22945번 팀 빌딩

🔒[문제 url]

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

🔑알고리즘

완전탐색을 진행할 경우, 두 개발자 사이의 사람 수와 두 개발자 중 더 작은 능력치 모두 증감을 반복하게 되므로 한 가지를 기준으로 삼아 계산한다.

• 따라서 두 개발자 사이의 사람 수를 기준으로 삼기위해,
  왼쪽 포인터를 첫번째 원소에, 오른쪽 포인터를 마지막 원소로 초기화하여 Two pointer를 진행한다.
  
  
• 포인터를 옮기는 기준은?
  • 두 개발자 중 더 능력치가 작은 개발자를 가리키는 포인터를 옮김으로써
    곱해지는 수를 키운다.
  • 즉, 왼쪽 포인터가 가리키는 개발자의 능력치가 더 작다면 왼쪽 포인터를 오른쪽으로 한 칸 옮긴다.
    오른쪽 포인터가 가리키는 개발자의 능력치가 더 작다면 오른쪽 포인터를 왼쪽으로 한 칸 옮긴다.
    
    
• 포인터를 양끝으로 초기화하는 이유는?
  • 두 개발자 사이의 사람 수를 기준으로 삼았기때문에,
    해당 기준을 [키우는 방향] 혹은 [줄이는 방향] 둘 중 하나로 정해야한다.
  • 키우는 방향으로 정하고자 할 경우, 포인터의 초기화 지점을 명확히 정할 수 없다.
  • 반면 줄이는 방향으로 정할 경우, 포인터의 초기화 지점은 반드시 양 끝이 된다.

🐾부분 코드

생략한다. 알고리즘을 이해한다면 구현은 쉽다.

🪄전체 코드

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

int n;
int a[100001];

void INPUT()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n;
    for(int i = 0; i < n; i++) cin >> a[i];
}


void SOLVE()
{

    int left = 0,right = n-1;
    int ans = 0;
    int v = 0;

    while(left < n - 1)
    {//왼쪽 포인터와 오른쪽 포인터 사이에 사람이 없다면 0이기때문에, n-1미만까지만 옮긴다.
        v = (right - left - 1) * min(a[left],a[right]);
        ans = max(ans,v);//최댓값 갱신

		// 능력치가 작은쪽을 바꿔
        if(a[left] < a[right]) left++;보자
        else right--;
    }

    cout << ans;
}

int main()
{
    INPUT();
    SOLVE();
}

🥇문제 후기

코딩테스트 기준, two pointer가 나온다면 아마 이 문제 수준이 최고 난이도가 아닐까싶다(주관적인 생각입니다!). two pointer는 유형이 다양하지 않으므로, 한 번에 몰아서 익혀두기를 추천한다. 완전탐색 외의 알고리즘을 떠올리기 쉽지는 않았던 문제같다. 그만큼 코테에서는 변별력이 매우 뛰어날 듯!!