[JAVA] 백준 q22945 - 팀 빌딩

22945번: 팀 빌딩

 

---

의식의 흐름

양 끝 개발자를 투 포인터가 가리키게 하면 될 것 같은데... 포인터 이동하는 조건을 어떻게 둬야하지..?
(결국 풀이 참고함) start와 end를 양 끝에서 시작해서 점차 가까워지도록 하면 되는거였는데 두 포인터를 앞에 두고 시작하는 방법만 생각했댱,,,

풀이 과정

1. 개발자 수(N)를 입력받는다.
2. N개의 개발자 능력치를 배열(ability)에 담아둔다.
3. 포인터를 이동하면서 최대 능력치(maxAbility)를 갱신한다.
3-1) start, end 포인터가 배열(ability)의 양 끝을 가리키게 둔다.
3-2) ability[start]와 ability[end]의 대소관계에 따라 포인터를 이동한다.
ability[start] < ability[end]인 경우, start 포인터를 오른쪽으로 이동시킨다.
ability[start] >= ability[end]인 경우, end 포인터를 왼쪽으로 이동시킨다.

start 포인터와 end 포인터가 서로 가까워지기 때문에 '개발자 A와 개발자 B 사이에 존재하는 다른 개발자 수'는 계속해서 감소한다. 따라서 'min(개발자 A의 능력치, 개발자 B의 능력치)'을 증가시키는 것에 초점을 두어야 한다.

4. maxAbility를 출력한다.

 

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
    public static int N;
    public static int[] ability;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        N = Integer.parseInt(br.readLine());
        ability = new int[N];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0;i<N;i++){
            ability[i] = Integer.parseInt(st.nextToken());
        }

        int start = 0;
        int end = N-1;
        int maxAbility = 0;
        while(start<end){
            maxAbility = Math.max(maxAbility, (end-start-1)*Math.min(ability[start],ability[end]));
            if(ability[start] < ability[end]){
                start++;
            }
            else{
                end--;
            }
        }
        bw.write(Integer.toString(maxAbility));
        bw.flush();

        br.close();
        bw.close();
    }
}