[백준] 2104번 부분배열 고르기

백준 2104번 부분배열 링크

문제 요약

1차원 배열이 주어지고, 배열에서 연속된 값들의 합(A[i] + A[i+1] + ... + A[j])과 연속된 값 중 가장 작은 값(min{A[i], A[i+1], ..., A[j]})을 곱한 것의 최대값을 구하는 문제이다. (백준 1725번 히스토그램 문제와 유사)

---

코드

import java.io.*;
public class Main {
    static long[] a;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        String[] datas = br.readLine().split(" ");
        a = new long[N];
        for (int i = 0 ; i < N ; i++)
            a[i] = Integer.parseInt(datas[i]);
        System.out.println(divide(0,N));
    }
    
    public static long divide(int start, int end){
        if (start == end)
            return 0;
        if (start + 1 == end)
            return (a[start] * a[start]);
        int mid = (start + end)/2;
        long result = Math.max(divide(start, mid), divide(mid,end));
        long w = a[mid];
        long h = a[mid];
        int l = mid;
        int r = mid;
        long h1;
        long h2;
        while (r - l + 1 < end - start){
            if (l > start)
               h1 = Math.min(a[l-1], h);
            else
                h1 = -1;
            if (r < end - 1)
                h2 = Math.min(a[r+1],h);
            else
                h2 = -1;
            if (h1 > h2)
            {
                h = h1;
                w += a[l-1];
                l--;
                result = Math.max(result, w*h1);
            }
            else
            {
                h = h2;
                w += a[r+1];
                r++;
                result = Math.max(result, w*h2);
            }
        }
        return result;
    }
}

---

문제 해결 방법

1. 주어진 배열의 시작(start)과 끝(end)을 파라미터로 받아 문제를 계속 절반으로 분할한다. (ex. divide(start, mid), divide(mid, end))

2. 분할이 log N 단계까지 이루어진 후 다시 병합이 이루어진다. 이 때 병합이 이루어지는 부분 배열의 좌측(start)으로부터의 최대 넓이와 우측(end)으로부터의 최대 넓이, 그리고 분할점(mid)에서 시작하는 최대 넓이를 비교하여 그 값을 return하며 올라가다보면 최종적으로 최대 넓이가 리턴된다.

---

이해를 돕기 위한 추가적인 내용
분할점(mid)에서 시작하는 최대 넓이를 구하는 과정은 divide 함수의 while문 내부를 통해 확인할 수 있다. 간략히 살펴보면 분할점의 좌우 높이를 비교하여 높이가 더 큰 쪽부터 방문하여 결국 start~end 구간을 전부 살펴본 후 가장 큰 값을 result에 저장하는 방식으로 최대 넓이를 저장하게 된다.