[백준] 2104번 : 부분배열 고르기 - C++ / JAVA

백준 2104 : 부분배열 고르기

등급 : Platinum V

2104번: 부분배열 고르기 (acmicpc.net)

2104번: 부분배열 고르기

사용 알고리즘 : Divide and Conquer

사용 자료구조 : Vector

 

세그먼트 트리로도 구현할 수 있는 문제이지만, 분할 정복으로 더 간단하게 구현할 수 있다.

 

크기가 9(인덱스 0~8)인 위의 배열을 예로 들어보자.

마지막 인덱스가 8이므로, MID값은 (0 + 8) ÷ 2인 4가 될 것이다.

그 이후 Left 부분을 재차 분할 정복을 하게 되면 이와 같이 될 것이다.

이를 계속 반복하게 되면 Left와 Right가 각각 한 점이 될 것이며, 이 때의 값은 각각 9가 된다.

( 구하려는 값이 구간 내 최솟값 * 구간 합이므로, 3 * 3인 9가 된다. )

분할 정복 연산을 끝내고 다시 그 앞 값으로 돌아갔을 때, Left의 부분배열의 최댓값이 될 수 있는 경우의 수는 3가지이다.

  1. 현재 구간의 Left 구간의 값

  2. 현재 구간의 Right 구간의 값

  3. 현재 구간의 Left와 Right 사이에 걸쳐있는 값

이때 우리가 집중해야 하는 경우는 걸쳐있는 경우에 대한 것이다.

위의 그림과 같이, Left와 Right 사이에 걸쳐있는 ?구간에 대한 값을 구하고 싶다고 해 보자.

이때 Mid ~ Mid + 1 구간, 즉 겹치는 구간 중 가장 짧은 구간을 현재 구간으로 지정하고, 구간을 점차 늘려줄 것이다.

구간을 늘리는 방식은 아래와 같다.

  1. 현재 구간의 좌 우 인덱스를 비교해 값이 더 큰 쪽으로 확장.

  2. 구간의 끝이 한 쪽 끝에 도달했다면 반대쪽으로 확장.

위의 방식을 따르면, 구간은 이와 같이 늘어난다. 이로 인해 구간을 Greedy하게 확장시키며 값을 구할 수 있다.

이와 같은 방식을 분할 정복으로 모든 구간에 적용시켜주고, 그에 대한 최댓값을 구하면 된다.

 

<hide/>
#include <iostream>
#include <vector>

using namespace std;
#define ll long long

int n;
vector <ll> v;
ll divq(int start, int end)
{
    if (start == end) return v[start] * v[start];
    else
    {
        int mid = (start + end) / 2;
        ll res_left = divq(start, mid);
        // 좌측 분할 정복의 결과
        ll res_right = divq(mid + 1, end);
        // 우측 분할 정복의 결과
        ll ret = max(res_left, res_right);
        // 좌측과 우측 중에 최댓값을 기록

        int left = mid;
        int right = mid + 1;
        // 중간값을 구하기 위해 걸쳐져 있는 구간의 인덱스를 부여

        ll min_value = min(v[left], v[right]);
        // 걸쳐진 인덱스의 크기는 2이므로, 두 인덱스 중 최솟값이 구간 최솟값
        ll sum = v[left] + v[right];
        ret = max(ret, min_value * sum);
        // 앞서 구한 최댓값과 현재 구한 사이 구간 값 중 최댓값을 기록

        while (left > start || right < end)
        // 둘 중에 하나라도 끝단에 도달하지 않은 경우
        {
            if (right < end && (start == left || v[left - 1] < v[right + 1]))
            // Left가 끝 단에 있거나 Left - 1 값 < Right + 1 값 일 때
            {
                right++;
                sum += v[right];
                min_value = min(min_value, v[right]);
            }
            else
            // Right가 끝 단에 있거나 Left - 1 값 >= Right + 1 값 일 때
            {
                left--;
                sum += v[left];
                min_value = min(min_value, v[left]);
            }
            ret = max(ret, min_value * sum);
            // 앞서 구한 최댓값과 현재 구한 사이 구간 값 중 최댓값을 기록
        }
        return ret;
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    v.resize(n);
    for (int i = 0; i < n; i++)
    {
        cin >> v[i];
    }
    cout << divq(0, n - 1);
}

<hide/>
import java.io.*;
import java.util.*;

public class Main {
    static List<Long> v = new ArrayList<>();
    static long divq(int start, int end)
    {
        if(start == end) return v.get(start) * v.get(start);
        else
        {
            int mid = (start + end)/2;
            long res_left = divq(start, mid);
            // 좌측 분할 정복의 결과
            long res_right = divq(mid+1, end);
            // 우측 분할 정복의 결과
            long ret = Math.max(res_left, res_right);
            // 좌측과 우측 중 최댓값을 기록

            int left = mid;
            int right = mid+1;
            // 중간값을 구하기 위해 걸쳐져 있는 부분의 인덱스를 부여
            long minValue = Math.min(v.get(left), v.get(right));
            // 걸쳐진 인덱스의 크기는 2이므로, 두 인덱스 중 최솟값이 구간 최솟값
            long sum = v.get(left) + v.get(right);
            ret = Math.max(ret, minValue * sum);
            // 앞서 구한 최댓값과 현재 구한 사이 구간 값 중 최댓값을 기록

            while(left > start || right < end)
            // 둘 중에 하나라도 끝에 도달하지 않은 경우
            {
                if(right < end && (left == start || v.get(left-1) < v.get(right+1)))
                // Left가 끝 단에 있거나 Left - 1 값 < Right + 1 값 일 때
                {
                    right++;
                    minValue = Math.min(v.get(right), minValue);
                    sum += v.get(right);
                }
                else
                // Right가 끝 단에 있거나 Left - 1 값 >= Right + 1 값 일 때
                {
                    left--;
                    minValue = Math.min(v.get(left), minValue);
                    sum +=  v.get(left);
                }
                ret = Math.max(ret, minValue * sum);
                // 앞서 구한 최댓값과 현재 구한 사이 구간 값 중 최댓값을 기록
            }
            return ret;
        }
    }

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

        int n = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());

        for(int i=0; i<n; i++)
        {
            v.add(Long.parseLong(st.nextToken()));
        }
        System.out.println(divq(0, n-1));
    }
}