BOJ_21758_꿀 따기 (Java)

[Gold V] 꿀 따기 - 21758

문제 링크

성능 요약

메모리: 25356 KB, 시간: 272 ms

분류

그리디 알고리즘, 누적 합

제출 일자

2025년 2월 26일 00:04:35

문제 설명

아래와 같이 좌우로 $N$개의 장소가 있다.

장소들 중 서로 다른 두 곳을 골라서 벌을 한 마리씩 둔다. 또, 다른 한 장소를 골라서 벌통을 둔다. 아래 그림에서 연한 회색의 장소는 벌이 있는 장소이고 진한 회색의 장소는 벌통이 있는 장소이다.

두 마리 벌은 벌통으로 똑바로 날아가면서 지나가는 모든 칸에서 꿀을 딴다. 각 장소에 적힌 숫자는 벌이 지나가면서 꿀을 딸 수 있는 양이다.

1. 두 마리가 모두 지나간 장소에서는 두 마리 모두 표시된 양 만큼의 꿀을 딴다. (벌통이 있는 장소에서도 같다.)
2. 벌이 시작한 장소에서는 어떤 벌도 꿀을 딸 수 없다.

위의 그림과 같이 배치된 경우 두 마리의 벌 모두 $4 + 1 + 4 + 9 + 9 = 27$의 꿀을 따서, 전체 꿀의 양은 54가 된다.

위의 그림과 같이 배치된 경우 왼쪽 장소에서 출발한 벌은 $9 + 4 + 4 + 9 + 9 = 35$의 꿀을 따고 오른쪽 장소에서 출발한 벌은 $4 + 9 + 9 = 22$의 꿀을 따므로, 전체 꿀의 양은 $57$이 된다.

위의 그림과 같은 경우는 전체 꿀의 양이 31이 된다.

장소들의 꿀 양을 입력으로 받아 벌들이 딸 수 있는 가능한 최대의 꿀의 양을 계산하는 프로그램을 작성하라.

입력

첫 번째 줄에 장소의 수 $N$이 주어진다.

다음 줄에 왼쪽부터 각 장소에서 꿀을 딸 수 있는 양이 공백 하나씩을 사이에 두고 주어진다.

출력

첫 번째 줄에 가능한 최대의 꿀의 양을 출력한다.

문제 풀이

코드

/**
 * Author: nowalex322, Kim HyeonJae
 */

import java.io.*;
import java.util.*;

public class Main {
    static BufferedReader br;
    static BufferedWriter bw;
    static StringTokenizer st;
    static int N, honey[], maxH, totalH, prefixSum[], max;
    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    public void solution() throws Exception {
        br = new BufferedReader(new InputStreamReader(System.in));
//        br = new BufferedReader(new InputStreamReader(new FileInputStream("src/main/java/BOJ_21758_꿀따기/input.txt")));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));

        N = Integer.parseInt(br.readLine());
        honey = new int[N];
        prefixSum = new int[N];
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++) {
            honey[i] = Integer.parseInt(st.nextToken());
            if(maxH < honey[i]) maxH = honey[i];
            totalH += honey[i];
        }

        // 벌통 맨 왼쪽
        // basket = 0, fixedBee = N-1;
        prefixSum[0] = honey[0];
        for(int i=1; i<=N-2; i++){
            prefixSum[i] = prefixSum[i-1] + honey[i];
        }
        for(int i=1; i<=N-2; i++){
            if(prefixSum[N-2] + (prefixSum[i-1] - honey[i]) > max) max = prefixSum[N-2] + prefixSum[i-1] - honey[i];
        }

        // 벌통 맨 오른쪽
        Arrays.fill(prefixSum, 0);
        prefixSum[N-1] = honey[N-1];
        for(int i=N-2; i>=1; i--){
            prefixSum[i] = prefixSum[i+1] + honey[i];
        }
        for(int i=1; i<=N-2; i++){
            if(prefixSum[1] + (prefixSum[i+1] - honey[i]) > max) max = prefixSum[1] + prefixSum[i+1] - honey[i];
        }

        // 벌 좌우 맨 끝
        max = Math.max(max, totalH - honey[0] - honey[N-1] + maxH);

        System.out.println(max);
        bw.flush();
        bw.close();
        br.close();
    }
}