문제 풀이

문제에서 개발자의 능력치가 다 다르다고 했는데 n은 10만이고 x는 최대 1만이다.
실제로 x는 최대 10만이 아닌가 싶다.

어쨌든 10000 x 10000으로는 문제가 풀리지 않아서 투포인터를 활용 했어야 했다.

시작점과 끝점에 각각 l과 r을 두고 l, r 위치의 능력치가 둘 중 누가 더 작은지 확인한다.
arr[l]이 더 작다면 r을 줄여 봤자 최소값은 arr[l]이고 간격이 줄어드니까 더 작은 값이 나올 수 밖에 없다.
arr[r]이 더 작다면 l을 올려 봤자 최소값은 arr[r]이고 간격이 줄어드니까 더 작은 값이 나올 수 밖에 없다.

그렇다면 l과 r 중 최소값이 위치해있는 쪽을 한칸 이동 시키면서 확인하면된다.

문제 링크

boj/22945

소스코드

PS/22945.java

    import java.io.*;
    import java.util.*;


    public class Main {
        static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));


        public static void main(String[] args) throws IOException {
            int n = Integer.parseInt(br.readLine());

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

            }

            int l = 0, r = n-1;
            int ans = 0;
            while(l<=r)
            {
                int min = Math.min(arr[l],arr[r]);
                ans = Math.max((r-l -1) * min, ans);
                if(arr[l] < arr[r])
                {
                    l++;
                }
                else
                {
                    r--;
                }

            }
            System.out.println(ans);
        }
    }