[백준 21758번] 꿀 따기 - JAVA

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

21758번: 꿀 따기

풀이

사용한 알고리즘 : 누적합(Prefix Sum)

 

풀이전략

1. 입력한 값들의 누적합을 새로운 배열에 저장한다.

2. 문제에서 구하는 최대의 꿀양이 나올 수 있는 경우는 아래의 세가지 중 하나의 경우이다.

  1) 벌 벌 꿀통

  좌측의 벌은 항상 배열의 최좌측에 위치, 꿀통은 배열의 최우측에 위치한다.

  중간의 벌을 이동시키며 가질 수 있는 최대 꿀양을 알아낸다.

 

 

  2) 꿀통 벌 벌

  꿀통은 항상 배열의 최좌측에 위치, 우측의 벌은 배열의 최우측에 위치한다.

  중간의 벌을 이동시키며 가질 수 있는 최대 꿀양을 알아낸다.

 

 

  3) 벌 꿀통 벌

  좌측의 벌은 항상 배열의 최좌측에 위치, 우측의 벌은 배열의 최우측에 위치한다.

  중간에 위치한 꿀통을 이동시키며 가질 수 있는 최대 꿀양을 알아낸다.

3. 위 3가지 경우의 수를 모두 탐색해보고, 그 중 가장 많은 꿀양을 얻었을 때의 값을 출력한다.

 

제출코드

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

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

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

        int graph[] = new int[N];
        for(int i=0;i<N;++i) graph[i]=Integer.parseInt(st.nextToken());

        int prefix_sum[] = new int[N];
        prefix_sum[0]=graph[0];
        for(int i=1;i<N;++i){
            prefix_sum[i]=prefix_sum[i-1]+graph[i];
        }

        int maxSum=0;
        for(int i=1;i<N-1;++i){
            if(maxSum<prefix_sum[N-1]-prefix_sum[0]-graph[i]+prefix_sum[N-1]-prefix_sum[i])
                maxSum=prefix_sum[N-1]-prefix_sum[0]-graph[i]+prefix_sum[N-1]-prefix_sum[i];
            if(maxSum<prefix_sum[N-1]-graph[N-1]-graph[i]+prefix_sum[i]-graph[i])
                maxSum=prefix_sum[N-1]-graph[N-1]-graph[i]+prefix_sum[i]-graph[i];
            if(maxSum<prefix_sum[i]-graph[0]+prefix_sum[N-2]-prefix_sum[i-1])
                maxSum=prefix_sum[i]-graph[0]+prefix_sum[N-2]-prefix_sum[i-1];
        }
        System.out.println(maxSum);
    }
}