백준 21758번 - 꿀 따기

문제

백준 21758번 - 꿀 따기

아이디어

• 각 장소의 꿀의 양은 모두 정수이므로 벌통과 벌과의 거리를 최대한 길게 하는 것이 최댓값을 구하기에 가장 유리하다.
• 벌통이 끝쪽에 위치하거나, 벌이 양쪽 끝에 있는 경우가 있을 것이다.
• 벌통이 끝쪽에 위치하는 경우 벌1을 반대편 끝쪽에 고정시키고 벌2의 위치를 옮겨가면서 값을 비교한다.
• 벌이 양쪽 끝에 있는 경우 벌통의 위치를 옮겨가면서 값을 비교한다.
• 특정 구간의 합을 구하는 것이기 때문에 누적합을 사용하면 쉽게 계산할 수 있다.

예상 시간 복잡도

• 예상 시간 복잡도 : O(N)

코드 구현

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BJ_21758 {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());

        int[] arr = new int[n + 1];
        long[] sum = new long[n + 1];

        StringTokenizer st = new StringTokenizer(br.readLine());

        for (int i = 1; i <= n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());

            sum[i] = arr[i] + sum[i - 1]; //누적 합
        }

        long max = Long.MIN_VALUE;

        //벌통이 가운데에 있고, 벌이 양 끝에 있는 경우
        for (int i = 2; i < n; i++) {
            long temp = (sum[i] - sum[1]) + (sum[n - 1] - sum[i - 1]);
            max = Math.max(max, temp);
        }

        //벌통이 첫번째에 있는 경우(왼쪽 끝)
        for (int i = 2; i < n; i++) {
            long temp = sum[i - 1] + (sum[n - 1] - arr[i]);
            max = Math.max(max, temp);
        }

        //벌통이 마지막에 있는 경우(오른쪽 끝)
        for (int i = 2; i < n; i++) {
            long temp = (sum[n] - sum[i]) + (sum[n] - sum[1] - arr[i]);
            max = Math.max(max, temp);
        }

        System.out.println(max);
    }
}