문제 링크
N개의 건물의 위치가 1부터 N이고 i번째 건물의 높이를 H(i)라 한다.
i < j일때, (H(i) + H(j)) * (j - i)의 최대값을 구해야한다.
모든 경우의 i, j를 구하면 O(N*N)이므로 시간초과이다. 따라서 i와 j의 범위를 제한할 방법을 생각해야한다.
1. 두 건물의 거리와 높이
N개의 건물중에서 두 건물의 높이합*거리가 최대인 i번째 건물과 j번째 건물을 찾았다고 할 때(i < j), i~j범위 밖의 건물은 건물i, j보다 작아야한다.
왜냐하면 최적의 i와 j를 찾았는데 그 밖의 범위에 더 크거나 같은 크기의 건물이 있다면 i~j 거리보다 더 큰 거리의 조합인 두 건물을 찾을수 있기 때문이다.
위의 논리에 따라 앞서는 건물(i에 해당하는 건물)은 위치가 증가할 수록 높이가 높아져야하며
뒤에 오는 건물은 위치가 증가할 수록 높이가 작아져야한다.
이를 만족하지 않는 건물들은 무시한다.
2. i를 기준으로 j를 분할정복
위의 방법으로 i에 해당하는 건물과 j에 해당하는 건물을 추려냈다면
특정 i의 최적인 j를 opt(i)라 할때, opt(i)는 opt(i)이상 위치에 있는 건물은 크기가 안되어서 더이상 최적이 아니라는 의미를 가지게 된다.
따라서 k < i일때 opt(k) <= opt(i) 이며,
k > i일때 opt(k) >= opt(i)이다.
이를 이용해 j의 범위를 줄여갈 수 있다.
import java.io.*;
import java.util.*;
public class Two_Buildings {
/**
* n개의 건물중 i와 j를 뽑는다.(i < j)
* 건물의 높이가 h일때
* (Hi + Hj) * (j - i)의 최대값을 구하라
* @param args
* @throws Exception
*/
static int N;
static ArrayList<Building> iB = new ArrayList<Building>(1000000);//x가 작아질 수록 h가 같거나 작게
static ArrayList<Building> jB = new ArrayList<Building>(1000000);//x가 커질 수록 h가 같거 작게
static long result = 0;
static class Building{
int x;
long h;
Building(int x, long h){this.x = x; this.h = h;}
}
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine());
for(int x = 1; x <= N; x++){
Building b = new Building(x, Long.parseLong(st.nextToken()));
/**
* j번째 빌딩보다 j+a번째 빌딩의 높이가 높다면 j번째 빌딩은 의미가 없다.
*/
while(!jB.isEmpty() && jB.get( jB.size() - 1 ).h < b.h) jB.remove(jB.size() - 1);
jB.add(b);
/**
* i번째 빌딩보다 i-a번째 빌딩의 높이가 높다면 i번째 빌딩은 필요가 없다.
*/
if(iB.isEmpty() || iB.get( iB.size() - 1 ).h < b.h) iB.add(b);
}
solve(0, iB.size() - 1, 0, jB.size() - 1);
System.out.println(result);
}
static void solve(int si, int ei, int sj, int ej){
if(si > ei) return;
int i = (si + ei) >> 1;
long value = Long.MIN_VALUE;
int opt = -1;
for(int j = sj; j <= ej; j++){
long val = cost(i, j);
if(value < val){
value = val;
opt = j;
}
}
result = Math.max(value, result);
solve(si, i - 1, sj, opt);
solve(i + 1, ei, opt, ej);
}
static long cost(int i, int j){
return (iB.get(i).h + jB.get(j).h) * (jB.get(j).x - iB.get(i).x);
}
}