자바(백준) 22945 팀 빌딩

오답 노트 & 새로 알게 된 점

이때까지 두 포인터 문제를 풀 때마다 항상 s와 e가 왼쪽 끝에서 시작하여 오른쪽 끝까지 가는 문제만 풀어보았다.

 

그래서 해당 문제를 보고 투 포인터로 풀어야겠다라는 생각이 들고,

한 시간동안 어떻게 풀어야하지 생각했다.

 

이 문제는 s와 e가 양쪽 끝에서 시작하는 투 포인터이다.

 

i * j의 최댓값을 구하려면 A도 최대, B도 최대여야한다.

 

여기서 그러면 s와 e 중에 어떤 기준으로 움직여야할까? 라는 생각을 해야한다.

 

A[i]와 A[j], 둘 중에 최대값을 움직여본다고 생각해보자.

그렇다면 결국에 min값은 그대로이거나 더 작아지게된다.

마찬가지로 둘의 사이가 가까워져 값이 줄어들게 된다.

결국 최대값을 움직일 필요가 없다.

 

---

코드

package TwoPointers;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class BOJ22945 {
    static int atoi(String str) {
        return Integer.parseInt(str);
    }
    static int N;
    static int A[];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        N = atoi(br.readLine());
 
        A = new int[N + 1];
 
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        for (int i = 1; i <= N; i++) {
            A[i] = atoi(st.nextToken());
        }
 
        pro();
    }
 
    static void pro() {
        int s = 1, e = N, max = 0;
 
        while (s <= e) {
            int abil = Math.min(A[s], A[e]) * (e - s - 1);
 
            max = Math.max(abil, max);
 
            if(A[s] > A[e]) e--;
            else s++;
        }
 
        System.out.println(max);
    }
}