[백준 22945] 팀 빌딩 (JAVA)

백준 22945번 문제 - 팀 빌딩

 

22945번: 팀 빌딩

---

문제 분석

 

 

• 개발자 2명 이상의 팀이 만들어져야하며,
  이 때 해당 팀의 능력치는 [양끝에 있는 개발자 중에 낮은 능력치 * 개발자 수 -2] 이다.
• 그럼 n명의 개발자가 순서 있이 주어졌을 때 가장 큰 팀 능력치를 구해라

---

해결 키 포인트

 

• 투포인트로 문제 풀이
• 개발 능력치는 양끝 사람의 능력치가 중요하므로 포인터를 양끝에 둔다.
• 포인터가 만났거나 추월했을 때 반복 종료되는 반복문
• 최대값과 비교해 현재 팀이 최대값이면 최대값 변경 아니면 이전 최대값 유지
  최대값 구하는 식 : max = Math.max(max, Math.min(startNum, endNum) * (end - start - 1));
• 양 끝 값 중에 작은 값을 이동
  (작은 값은 최대값을 만드는데 도움이 안됨)

 

투포인터 문제에 중점

 

• 투포인터를 양끝에 둘지, 맨 앞에 같이 둘지 정하는게 중요 !
  나도 아직 잘 모르지만 간단하게 생각하면 다음과 같은 것 같다.
  
  • 맨 앞 : 연속된 구간에 관한 문제
  • 양 끝 : 맨 끝에 값이 중요할 때

 

코드

 

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        int [] nums = new int[N+1];

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

        int start = 1;
        int end = N;
        int max = 0;

        while(start < end) {
            int startNum = nums[start];
            int endNum = nums[end];
            max = Math.max(max, Math.min(startNum, endNum) * (end - start - 1));

            if(startNum > endNum) {
                end--;
            }
            else  {
                start++;
            }
        }
        System.out.println(max);
    }
}