[백준] 21758번: 꿀따기-JAVA

문제 바로 가기 > 백준 2178번 꿀따기

 

 

그리디 + 누적합을 이용해 푸는 문제이다.

 

총 3가지 경우가 있다.

1. 벌 - 벌 - 벌통: 벌 1을 맨 왼쪽에 벌통을 맨 오른쪽에 고정 -> 벌 2를 자유롭게 배치
2. 벌통 - 벌 - 벌: 벌 1을 맨 오른쪽에 벌통을 맨 왼쪽에 고정 -> 벌 2를 자유롭게 배치
3. 벌 - 벌통 - 벌 : 벌을 모두 양 끝쪽에 고정 -> 벌통을 자유롭게 배치

이때 각 벌이 지나갈 때 꿀을 먹을 수 있는 양은 누적합으로 계산해야 한다!

import java.util.Arrays;
import java.util.Scanner;

public class _21758 {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int[] honey=new int[n];
        for(int i=0;i<n;i++){
            honey[i]=sc.nextInt();
        }
        int[] prefix=new int[n]; //누적합
        int max=Integer.MIN_VALUE;
        prefix[0]=honey[0];
        for(int i=1;i<n;i++){
            prefix[i]=prefix[i-1]+honey[i];
        }
        //벌 - 벌 - 벌통
        for(int i=1;i<honey.length-1;i++){
            int sum=(prefix[n-1]-honey[0]-honey[i])+(prefix[n-1]-prefix[i]);
            max=Math.max(sum,max);
        }

        //벌통- 벌 -벌
        for(int i=1;i<honey.length-1;i++){
            int sum=(prefix[n-2]-honey[i])+(prefix[i-1]);
            max=Math.max(sum,max);
        }

        //벌 - 벌통 -벌
        for(int i=1;i<honey.length-1;i++){
            //왼쪽
            int sum=prefix[i]+(prefix[n-2]-prefix[i-1])-honey[0];
            max=Math.max(sum,max);
        }

        System.out.println(max);
    }
}