백준 22945 [자바] java 팀 빌딩

문제 링크: https://www.acmicpc.net/problem/22945

22945번: 팀 빌딩

▶문제

능력치가 다 다른 개발자 N명이 팀 빌딩을 위해 한 줄로 서있다.

하나의 팀을 만들기 위해서는 개발자 2명이 반드시 모여야 한다.

개발자 A와 개발자 B가 팀을 만들 때 팀의 능력치는 아래와 같이 계산이 된다.

• (개발자 A와 개발자 B 사이에 존재하는 다른 개발자 수) × min(개발자 A의 능력치, 개발자 B의 능력치)

예를 들어, 4명의 개발자가 존재할 때, 각 개발자의 능력치를 1 4 2 5라고 하자. 이때 능력치가 1인 개발자와 능력치가 5인 개발자가 한 팀을 이뤘다고 가정하자. 그러면 이 팀의 능력치는 2×min(1,5)=22 ×min(1,5)=2 ×min(1, 5) = 2$가 된다.

팀 빌딩에서 나올 수 있는 팀 중 능력치의 최댓값을 구해보자.

---

▶입력

첫 번째 줄에 개발자의 수 N이 주어진다.

두 번째 줄에는 N의 개발자의 각 능력치 xi가 공백으로 구분되어 주어진다.

---

▶출력

팀의 능력치 최댓값을 출력한다.

---

▶해설

N의 최대 입력값이 100,000이므로 브루트 포스로는 시간 초과가 발생합니다. 투 포인터를 이용하여 풉니다.

 

변수 설정

int [] arr = new int[n+1]

int left = 1  // 왼쪽 시작 지점

int right = n // 오른쪽 시작 지점

 

만약 arr[left], arr[right]의 경우 팀 빌딩의 값은 (right-left-1)*Math.min(arr[left], arr[right])가 됩니다. 

 

이때 둘 중에 큰 값을 가리키는 포인터를 이동시켜도 최솟값은 변하지 않으므로 오히려 팀 빌딩 값이 작아집니다.

 

따라서 arr[left], arr[right] 중 작은 값을 가지는 포인터를 이동시키며, 진행했을 때 최댓값을 구할 수 있습니다. 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int n;
    static int [] arr;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        arr = new int [n+1];
        String[] str = br.readLine().split(" ");
        for(int i=1; i<=n; i++){
            arr[i] = Integer.parseInt(str[i-1]);
        }

        int result = solve();
        System.out.println(result);

    }

    private static int solve(){
        int left = 1;
        int right = n;
        int result=0;

        while (left<=right){
            int min = Math.min(arr[left],arr[right]);
            result = Math.max(min*(right-left-1), result);
            if(arr[left]<arr[right]){
                left++;
            }
            else{
                right--;
            }
        }
        return result;
    }
}

지금까지 투 포인터 문제들은 항상 같은 지점에서 시작하는 방식이었는데, 이 문제는 시작 지점이 달라서 새로운 유형이었습니다.