[알고리즘] 백준 2104 - 부분 배열 고르기

문제본문

문제해설

문제에서의 N의 범위는 100,000 이하입니다. 따라서 N^2 인 완전탐색으로는 시간초과가 발생할 수 있습니다.


분할 정복은 문제의 범위를 2이상으로 나누어 부분적으로 정복하여 푸는 방법입니다. 최대의 점수를 갖는 부분배열을 구하는 이 문제에 적용하여 중앙 값을 기준으로 3가지 경우에서 최대값을 구하면 됩니다.

1. 중앙값을 포함하는 부분 배열

이 경우는 중앙 값을 포함하는 부분 배열의 점수를 구하는 방법입니다. 히스토그램 풀이법과 유사하고 처음 중앙값하나 존재하는 배열에서 왼쪽, 또는 오른쪽으로 하나씩 요소들을 포함시키면서 최대값을 찾는 방법입니다.

 

왼쪽이나 오른쪽으로 이동하는 기준은 부분배열의 점수 공식을 참고하면 큰 요소를 포함하는 것이 무조건 최대 점수로 가는 길이 됩니다. 그런데 한쪽방향으로만 증가하면 안되기 때문에 While 반복문의 조건을 잘 설정해 주어야 합니다.

            (중략)..
            long sum = arr[mid];
            long min = arr[mid];
            int l = mid, r = mid; //l은 왼쪽, r은 오른쪽

            while(r - l < end - start) {
                long lValue = l > start ? arr[l - 1] : -1; //요소는 음수를 포함하지 않음, 따라서 한쪽방향으로 모두 이동한 후, 값이 작아도 반대쪽 으로 이동할 수 있게끔 -1을 부여함
                long rValue = r < end ? arr[r + 1] : -1; //요소는 음수를 포함하지 않음

                if (lValue > rValue) {
                    sum += lValue;
                    min = Math.min(min, lValue);
                    l--;
                } else {

                    sum += rValue;
                    min = Math.min(min, rValue);
                    r++;
                }

                result = Math.max(result, sum * min);
            }

 

2. 중앙값을 포함하지 않는 부분배열

처음 문제해설에서 3가지의 경우의 최대값을 구하면 된다고 했고, 앞서 말한 중앙값을 포함하는 경우가 포함됩니다.
나머지 2가지 경우는 유사하기 때문에 한번에 설명 드리겠습니다.

현재 중앙값을 포함하지 않는 부분 배열을 구하기 위해서 분할 정복의 원리처럼 탐색하고자 하는 배열의 범위를 나누면 됩니다. 나누는 기준은 중앙값으로 설정합니다.

         if (start > end) return -1;   //재귀함수 종료조건
        else if (start == end) return arr[start] * arr[start];
        else {
            int mid = (start + end) / 2;
            long result = Math.max(division(mid + 1, end, arr), division(start, mid - 1, arr)); //최대값 측정

 

전체 코드

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();

        long[] arr = new long[n];
        for (int i = 0; i < n; i++) {
            arr[i] = scanner.nextInt();
        }

        System.out.println(division(0, n - 1, arr));
    }

    public static long division(int start, int end, long[] arr) {
        if (start > end) return -1;
        else if (start == end) return arr[start] * arr[start];
        else {
            int mid = (start + end) / 2;
            long result = Math.max(division(mid + 1, end, arr), division(start, mid - 1, arr));

            long sum = arr[mid];
            long min = arr[mid];
            int l = mid, r = mid;

            while(r - l < end - start) {

                long lValue = l > start ? arr[l - 1] : -1;
                long rValue = r < end ? arr[r + 1] : -1;

                if (lValue > rValue) {
                    sum += lValue;
                    min = Math.min(min, lValue);
                    l--;
                } else {

                    sum += rValue;
                    min = Math.min(min, rValue);
                    r++;
                }

                result = Math.max(result, sum * min);
            }

            return result;
        }
    }
}

 

참고

• 분할 정복 - Ries