백준 21758번 - 꿀 따기 (java)

💡 문제 링크

https://www.acmicpc.net/problem/21758

 

 

💡 아이디어

총 3가지 케이스가 있다.

 

1. 벌1-벌2-벌통

• 최대 꿀의 양이 되려면 우선 벌1이 왼쪽 끝, 벌통이 오른쪽 끝에 위치해야 한다. (아니라면 양끝에 더해지지 않는 값이 생기므로)
• 결국엔 벌2의 위치를 바꿔가며 최댓값을 찾아야 한다.

2. 벌통-벌2-벌1

• 최대 꿀의 양이 되려면 우선 벌통이 왼쪽 끝, 벌1이 오른쪽 끝에 위치해야 한다.
• 나머지는 1번 케이스와 동일하다.

3. 벌1-벌통-벌2

• 최대 꿀의 양이 되려면 우선 벌1이 왼쪽 끝, 벌2가 오른쪽 끝에 위치해야 한다. (아니라면 양끝에 더해지지 않는 값이 생기므로)
• 이 경우의 합은 arr[1] ~ arr[N-2] 까지의 합 + 벌통의 값 이므로 arr[1]~ arr[N-2]의 값 중 최댓값의 위치에 벌통을 두면 된다.

 

💡 코드

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

public class BOJ_G5_21758_꿀따기 {
    public static int N;
    public static int[] arr;
    public static int maxSum;

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

        int sum = 0;
        int max = 0;

        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
            if (i == 0 || i == N - 1) {
                continue;
            }
            if (arr[i] > max) {
                max = arr[i];
            }
            sum += arr[i];
        }

	//벌1-벌2-벌통
        int sum1 = sum + arr[N - 1];
        int tempSum = 0;
        for (int i = 1; i < N; i++) {
            int bee2 = arr[i];
            int bee1Sum = sum1 - bee2;
            int bee2Sum = sum1 - (tempSum + bee2);
            if (bee1Sum + bee2Sum > maxSum) {
                maxSum = bee1Sum + bee2Sum;
            }
            tempSum += bee2;
        }

	//벌통-벌2-벌1
        int sum2 = sum + arr[0];
        int tempSum2 = 0;
        for (int i = N - 2; i >= 0; i--) {
            int bee2 = arr[i];
            int bee1Sum = sum2 - bee2;
            int bee2Sum = sum2 - (tempSum2 + bee2);
            if (bee1Sum + bee2Sum > maxSum) {
                maxSum = bee1Sum + bee2Sum;
            }
            tempSum2 += bee2;
        }

	//벌1-벌통-벌2
        if (sum + max > maxSum) {
            maxSum = sum + max;
        }
        
        System.out.println(maxSum);
    }
}