[BaekJoon 17425번 / JAVA] 꿀 따기

Question

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

21758번: 꿀 따기

 

---

💡 Solution

다음과 같은 3가지 경우가 있습니다.

 

1. 벌통이 왼쪽 끝에 존재할 경우

: 이 경우에는 벌1은 반드시 오른쪽 끝에 존재해야 합니다. 벌은 반드시 벌통 쪽으로 이동해야하는데, 최대한 한 장소라도 더 거쳐서 꿀을 더 따야하기 때문입니다. 벌1의 위치는 정해졌으니, 벌2의 위치만 탐색하면 됩니다.

 

2. 벌통이 오른쪽 끝에 존재할 경우

: 1번과 반대로 벌1은 반드시 왼쪽 끝에 존재해야 합니다. 동일하게 벌2의 위치만 탐색하면 됩니다.

 

3. 벌통이 가운데에 있을 경우

: 이 경우에 벌1과 벌2는 반드시 양쪽 끝에 존재해야 합니다. 만일 [2, 3, 4, 5, 6]이 있고 벌통이 4 위치에 있을 때 벌1이 3에 있고 벌2가 5에 있다면, 2와 6은 쓸모없게 되어버립니다. (꿀을 많이 따야하는데 !) 이때는 벌통의 위치를 탐색합니다.

이때 각 위치에서의 누적합을 왼쪽, 오른쪽 방향으로 각각 구해놓으면 위 3가지의 경우에 대해 다루기 쉽습니다.

 

💻 Code

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

public class BJ17425 {
	static int N;
	static int[] honey;
	static int[] toRightSum, toLeftSum;
	static int total;
	static int max;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		N = Integer.parseInt(br.readLine());
		honey = new int[N];
		toRightSum = new int[N];
		toLeftSum = new int[N];
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int temp = 0;
		for (int i = 0; i < N; i++) {
			honey[i] = Integer.parseInt(st.nextToken());
			temp += honey[i];
			toRightSum[i] = temp;
		}
		
		temp = 0;
		for (int i = N - 1; i >= 0; i--) {
			temp += honey[i];
			toLeftSum[i] = temp;
		}
		
		total = toRightSum[N - 1];
		max = 0;
		
		leftEndBeehive();
		rightEndBeehive();
		middleBeehive();
		
		System.out.println(max);
		
		
	}
	
	//벌통이 왼쪽 끝에 있을 경우(벌1은 반드시 오른쪽 끝에 존재)
	public static void leftEndBeehive() {
		int bee1 = 0;
		int bee2 = 0;
		
		//벌2의 위치 결정 위해 탐색
		for (int i = N - 2; i >= 1; i--) {
			bee1 = total - honey[N - 1] - honey[i];
			bee2 = total - toLeftSum[i];
			max = Math.max(max, bee1 + bee2);
		}
	}
	
	//벌통이 오른쪽 끝에 있을 경우(벌1은 반드시 왼쪽 끝에 존재)
	public static void rightEndBeehive() {
		int bee1 = 0;
		int bee2 = 0;
		
		//벌2의 위치 결정 위해 탐색
		for (int i = 1; i < N - 1; i++) {
			bee1 = total - honey[0] - honey[i];
			bee2 = total - toRightSum[i];
			max = Math.max(max, bee1 + bee2);
		}
	}
	
	//벌통이 가운데에 있을 경우(벌1과 벌2는 반드시 양끝에 존재)
		public static void middleBeehive() {
			int bee1 = 0;
			int bee2 = 0;
			
			//벌통 위치 결정 위해 탐색
			for (int i = 1; i < N - 1; i++) {
				bee1 = toRightSum[i] - honey[0];
				bee2 = toLeftSum[i] - honey[N - 1];
				max = Math.max(max, bee1 + bee2);
			}
		}

}