백준 21758: 꿀따기 [Java] - 포포

문제

문제 링크

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

21758번: 꿀 따기

---

문제에서 주어진 장소의 크기(N)은 최대 100,000이므로
O(N*N)보다 시간복잡도가 크거나 같은 풀이로는 해결할 수 없습니다.

풀이의 핵심은 벌 두마리와 꿀통의 위치가 가능한 경우의 수를 전부 따져보는 것입니다.
[1] 벌 - 벌 - 꿀통

[2] 벌 - 꿀통 - 벌

[3] 꿀통 - 벌 - 벌

총 3가지의 경우가 존재합니다. 이 3가지 경우를 전부 검사한다면, 벌 두마리가 획득할 수 있는 꿀의 최대값을 얻어낼 수 있습니다. 

1번과 3번의 경우에서 벌 한마리와 꿀통은 반드시 양 끝에 위치하고 있어야합니다. 최대한 많은 꿀을 획득해야하므로, 탐색하지 못하는 장소가 있어서는 안됩니다. 벌은 꿀통을 만나는 순간 탐색을 종료하며, 꿀통 방향으로만 날아가기 때문입니다.
2번 경우에서는 벌을 양 끝에 두고, 꿀통의 위치를 옮겨가며 최대값을 찾으면 됩니다.

최대값을 찾을 때, 누적합을 사용합니다. 

위와 같이 벌 - 벌 - 꿀통 경우를 예시로 들면
벌1이 꿀통까지 날아가며 획득할 수 있는 꿀의 양은 배열의 1~9에 담긴 꿀의 양입니다(출발하는 위치에서는 얻을 수 없습니다)
벌2가 꿀통까지 날아가며 획득할 수 있는 꿀의 양은 배열의 5~9에 담긴 꿀의 양입니다.

int[] sum에 누적합을 저장한다면 
벌1이 획득하는 꿀의 양 = sum[9] - sum[벌1의 위치]
벌2가 획득하는 꿀의 양 = sum[9] - sum[벌2의 위치] 로 구할 수 있습니다. 

public class Bee {

	static int arr[];
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;
		int n = Integer.parseInt(br.readLine());
		st = new StringTokenizer(br.readLine());

		arr = new int[n + 1];
		for (int i = 1; i < arr.length; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}

		int left = leftHoney();  //꿀통 - 벌 - 벌
		int right = rightHoney(); //벌 - 벌 - 꿀통
		int mid = midHoney(); // 벌 - 꿀통 - 벌

		int max = Math.max(left, Math.max(right, mid));
		System.out.println(max);

	}

	public static int leftHoney() { //꿀통 - 벌 - 벌
		int sum[] = new int[arr.length]; // 누적합을 저장할 배열

		for (int i = arr.length - 2; i >= 1; i--) {
			sum[i] = sum[i + 1] + arr[i + 1];
		}

		int endSum = sum[1];

		int max = 0;

		for (int i = 2; i < arr.length; i++) {
			max = Math.max(max, endSum - arr[i] + sum[i]);
		}

		return max;
	}

	public static int rightHoney() { //벌통이 왼쪽에 위치
		int sum[] = new int[arr.length]; // 누적합을 저장할 배열

		for (int i = 2; i < arr.length; i++) {
			sum[i] = sum[i - 1] + arr[i - 1];
		}

		int endSum = sum[arr.length - 1];
		int max = 0;

		for (int i = 1; i < arr.length - 1; i++) {
			max = Math.max(max, endSum - arr[i] + sum[i]);
		}

		return max;
	}

	public static int midHoney() { //벌통이 가운데에 위치
		int leftSum[] = new int[arr.length];
		int rightSum[] = new int[arr.length];

		for (int i = 2; i < leftSum.length; i++) {
			leftSum[i] = leftSum[i - 1] + arr[i];
		}

		for (int i = rightSum.length - 2; i >= 1; i--) {
			rightSum[i] = rightSum[i + 1] + arr[i];
		}

		int max = 0;

		for (int i = 1; i < arr.length; i++) {
			max = Math.max(max, leftSum[i] + rightSum[i]);
		}

		return max;
	}
}