[BaekJoon] 21758 꿀 따기 (Java)

1.  문제 링크

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

2.  문제

요약

• 좌우로 N개의 장소가 있고 장소들 중 서로 다른 두 곳을 골라서 벌을 한 마리씩 둡니다.
• 또, 다른 한 장소를 골라서 벌통을 둡니다.
• 두 마리 벌은 벌통으로 똑바로 날아가면서 지나가는 모든 칸에서 꿀을 땁니다.
• 각 장소에 적힌 숫자는 벌이 지나가면서 꿀을 딸 수 있는 양입니다.
• 장소들의 꿀 양을 입력으로 받아 벌들이 딸 수 있는 가능한 최대의 꿀의 양을 계산하는 문제입니다.
• 입력: 첫 번째 줄에 3보다 크거나 같고 100,000보다 작거나 같은 장소의 수 N이 주어지고 두 번째 줄에 1보다 크거나 같고 10,000보다 작거나 같은 정수인 각 장소에서 꿀을 딸 수 있는 양이 주어집니다.
• 출력: 첫 번째 줄에 가능한 최대의 꿀의 양을 출력합니다.

3.  소스코드

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

public class Main {
	static StringBuilder sb = new StringBuilder();
	static int n;
	static int[] honey;
	static int[] accumulate;
	
	static void input() {
		Reader scanner = new Reader();
		n = scanner.nextInt();
		honey = new int[n];
		accumulate = new int[n];
		for(int i = 0; i < n; i++) {
			honey[i] = scanner.nextInt();
		}
	}
	
	static void solution() {
		accumulation();
		int max = Integer.MIN_VALUE;
		for(int i = 1; i < n - 1; i++) {
			max = Math.max(max, leftToRight(i));
		}
		for(int i = 1; i < n - 1; i++) {
			max = Math.max(max, rightToLeft(i));
		}
		for(int i = 1; i < n - 1; i++) {
			max = Math.max(max, bothSides(i));
		}
		sb.append(max);
	}
	
	static void accumulation() {
		accumulate = honey.clone();
		for(int i = 1; i < n; i++) {
			accumulate[i] += accumulate[i - 1];
		}
	}
	
	static int leftToRight(int bee) {
		return ((accumulate[n - 1] - honey[0] - honey[bee]) + (accumulate[n - 1] - accumulate[bee]));
	}
	
	static int rightToLeft(int bee) {
		return ((accumulate[n - 2] - honey[bee]) + accumulate[bee - 1]);
	}
	
	static int bothSides(int hive) {
		return ((accumulate[hive] - honey[0]) + (accumulate[n - 2] - accumulate[hive - 1]));
	}
	
	public static void main(String[] args) {
		input();
		solution();
		System.out.println(sb.toString());
	}
	
	static class Reader {
		BufferedReader br;
		StringTokenizer st;
		
		public Reader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}
		String next() {
			while(st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch (IOException e) {
					// TODO Auto-generated catch block
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}
		int nextInt() {
			return Integer.parseInt(next());
		}
	}
}

4.  접근

• 주어진 꿀의 양들에 대해 누적 합을 구하고 이를 이용하여 문제를 해결합니다.
• 두 마리의 벌이 꿀을 따는 경우를 생각해보면 3가지 경우가 존재합니다.
  1. 두 마리의 벌이 모두 벌통 왼쪽에 있는 경우
  2. 두 마리의 벌이 모두 벌통 오른쪽에 있는 경우
  3. 벌통 양 쪽에 벌이 한 마리씩 있는 경우
• 최대로 꿀을 따야하기 때문에 위 세 가지 경우에서 벌통과 한 마리의 벌 위치 또는 두 마리의 벌의 위치를 지정할 수 있습니다.
• 1번의 경우는 벌통이 가장 오른쪽 위치에 존재하고 한 마리의 벌은 가장 왼쪽 위치에 존재해야 꿀을 딸 수 있는 위치들이 많아지고 그에 따라 최대로 벌을 딸 수 있기 때문에 이렇게 배치를 해놓고 다른 한 마리의 벌의 위치를 찾습니다.
• 2번의 경우는 벌통이 가장 왼쪽 위치에 존재하고 한 마리의 벌은 가장 오른쪽 위치에 존재해야 꿀을 딸 수 있는 위치들이 많아지고 그에 따라 최대로 벌을 딸 수 있기 때문에 이렇게 배치를 해놓고 다른 한 마리의 벌의 위치를 찾습니다.
• 3번의 경우는 두 마리의 벌이 각각 가장 왼쪽 위치와 가장 오른쪽 위치에 존재해야 꿀을 딸 수 있는 위치들이 많아지고 그에 따라 최대로 벌을 딸 수 있기 때문에 이렇게 배치를 해놓고 벌통의 위치를 찾습니다.

  ---

  9

  9

  4

  1

  4

  9

  9

• 위와 같이 꿀의 양이 주어졌을 때, 이러한 예를 통해 각각의 경우에 최대로 딸 수 있는 꿀의 양을 어떻게 구하는지 확인합니다.
• 주어진 꿀의 양에 대해 누적 합을 진행하면 아래와 같이 결과가 나옵니다.

  9

  18

  22

  23

  27

  36

  45

• 주어진 꿀의 양을 넣어놓은 배열을 honey, 주어진 꿀의 양들에 대해 누적 합을 구한 배열을 accumulate라고 하겠습니다.

  ---

• 1번의 경우에는 왼쪽 끝 위치에 한 마리의 벌이 존재하고 오른쪽 끝 위치에 벌통이 위치하도록 배치합니다.
• 그럴 때, 예를 들어 다른 한 마리의 벌이 3번째 위치에 존재한다면 아래와 같이 구할 수 있습니다. 왼쪽 끝 위치에 존재하는 벌을 1번 벌, 3번째 위치에 존재하는 벌을 2번 벌이라고 하겠습니다.
  • 1번 벌: 9 + 1 + 4 + 9 + 9 = 32
  • 2번 벌: 1 + 4 + 9 + 9 = 23
• 위에서 구한 꿀의 양을 수식으로 표현할 수 있습니다.
  • 1번 벌: accumulate[n] - honey[1번 벌 위치] - honey[2번 벌 위치]
  • 2번 벌: accumulate[n] - accumulate[2번 벌 위치]
• 위 수식을 이용하여 두 번째 벌의 위치를 이동해가며 최대로 딸 수 있는 꿀의 양을 구합니다.

  ---

• 2번의 경우에는 오른쪽 끝 위치에 한 마리의 벌이 존재하고 왼쪽 끝 위치에 벌통이 위치하도록 배치합니다.
• 그럴 때, 예를 들어 다른 한 마리의 벌이 4번째 위치에 존재한다면 아래와 같이 구할 수 있습니다. 오른쪽 끝 위치에 존재하는 벌을 1번 벌, 4번째 위치에 존재하는 벌을 2번 벌이라고 하겠습니다.
  • 1번 벌: 9 + 4 + 4 + 9 + 9 = 35
  • 2번 벌: 4 + 9 + 9 = 22
• 위에서 구한 꿀의 양을 수식으로 표현할 수 있습니다.
  • 1번 벌: accumulate[n] - honey[2번 벌 위치]
  • 2번 벌: accumulate[2번 벌 위치 - 1]
• 위 수식을 이용하여 두 번째 벌의 위치를 이동해가며 최대로 딸 수 있는 꿀의 양을 구합니다.

  ---

• 3번의 경우에는 두 마리의 벌이 각각 가장 왼쪽 위치와 가장 오른쪽 위치에 위치하도록 배치합니다.
• 그럴 때, 예를 들어 벌통이 4번째 위치에 존재한다면 아래와 같이 구할 수 있습니다. 왼쪽 끝 위치에 존재하는 벌을 1번 벌, 오른쪽 끝 위치에 존재하는 벌을 2번 벌이라고 하겠습니다.
  • 1번 벌: 9 + 4 + 1 = 14
  • 2번 벌: 9 + 4 + 1 = 14
• 위에서 구한 꿀의 양을 수식으로 표현할 수 있습니다.
  • 1번 벌: accumulate[벌통의 위치] - honey[1]
  • 2번 벌: accumulate[n] - accumulate[벌통의 위치 - 1] - honey[n] = accumulate[n - 1] - accumulate[벌통의 위치 - 1]
• 위 수식을 이용하여 벌통의 위치를 이동해가며 최대로 딸 수 있는 꿀의 양을 구합니다.