[백준] 꿀 따기

1. 문제 요약

• N개의 꿀을 담는 공간이 주어지고, 각 공간에는 꿀의 양을 의미하는 숫자가 표시됩니다.
• N개 중 "하나"의 공간에는 벌집이 있고, 2마리의 꿀벌은 서로 다른 공간에서 시작해 벌집으로 이동합니다.
• 꿀벌은 벌집으로 이동하면서 시작점을 제외한 공간에 대해 꿀을 수집할 수 있습니다.
• 수집 가능한 최대의 꿀의 양을 구하는 문제입니다.

입력 파라미터

• `int N`
• `int[] honeys`

반환 타입

• `int maxHoney`

예제

• N: 7
• honeys: [9, 9, 4, 1, 4, 9, 9]
• return: 57

주의 사항

• 이 문제의 경우, 중첩 for문을 이용해 모든 위치를 계산하는 방식으로 풀 수 있지만 시간 효율성을 통과하지 못합니다.
• 따라서 구간 합 알고리즘을 활용해 단일 for문을 문제를 풀어야 합니다.

2. 문제 풀이

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;

public class Main {

  public static void main(String[] args) throws IOException {
    try (
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    ) {
      int N = Integer.parseInt(br.readLine());
      int[] honeys = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
      int[] prefixSum = new int[N];

      prefixSum[0] = honeys[0];
      for (int i = 1; i < N; i++) {
        prefixSum[i] = prefixSum[i-1] + honeys[i];
      }

      int maxHoney = 0;
      // Case 1: 벌(1)-벌(2)-벌통
      for (int bee2 = 1; bee2 < N-1; bee2++) {
        int bee1Honey = prefixSum[N-1] - honeys[0] - honeys[bee2];
        int bee2Honey = prefixSum[N-1] - prefixSum[bee2];
        maxHoney = Math.max(maxHoney, bee1Honey + bee2Honey);
      }

      // Case 2: 벌통-벌(1)-벌(2)
      for (int bee1 = N-2; bee1 > 0; bee1--) {
        int bee1Honey = prefixSum[bee1] - honeys[bee1];
        int bee2Honey = prefixSum[N-1] - honeys[bee1] - honeys[N-1];
        maxHoney = Math.max(maxHoney, bee1Honey + bee2Honey);
      }

      // Case 3: 벌(1)-벌통-벌(2)
      for (int hive = 1; hive < N-1; hive++) {
        int bee1Honey = prefixSum[hive] - honeys[0];
        int bee2Honey = prefixSum[N-1] - prefixSum[hive-1] - honeys[N-1];
        maxHoney = Math.max(maxHoney, bee1Honey + bee2Honey);
      }

      bw.write(String.valueOf(maxHoney));
    }
  }

}

 

시간 복잡도

• 시간 복잡도: `O(N)`
  • Prefix Sum 계산: 단일 for문을 사용해 prefixSum 배열을 채우는 작업이 `O(N)`입니다.
  • 각 경우별 최대 꿀 수집량 계산: 세 가지 경우(Case 1, Case 2, Case 3)에 대해 각각 단일 for문을 사용해 시간 복잡도는 `O(N)`입니다.