백준 - 꿀 따기

문제 설명

---

주어진 배열은 각 꿀의 양을 나타낸다.

벌 2마리 벌통 1개가 주어진다.

벌 2마리를 어느 위치에 위치시키고, 벌통을 벌2마리의 위치가 아닌 위치에 두면, 벌들이 벌통을 향해서 이동하게 된다. 단, 가는 길의 꿀을 따면서 간다.

이런 시스템으로 이동할 경우 벌들이 꿀을 딸 수 있는 가능한 최대 양을 구하는 문제이다.

처음 접근할 때 어떤 것을 고정시켜야 될까? 라는 질문에 답하지 못했다.

너무나도 애매했다.

왜냐하면 벌들의 위치와 꿀통의 위치에 따라 달라지는데, n^3 이 나온다고 생각했다.

- 벌1,2 위치 선택 (n^2) - > 꿀통 위치 [i, n-1] (n)

그래서 시간초과가 분명하게 난다고 생각했다.

최대가 되는 경우를 생각해 볼때, “꿀벌 1 위치 < 꿀벌 2위치 <꿀통의 위치” 일 때, 꿀통까지 누적합 - 꿀벌 1 위치 - (꿀벌 2위치) 추가로 뺴줄 경우를 생각하면 꿀벌 2가 위치할때는 최대한 적은 양의 꿀을 위치시키는것이 유리할 수 있겠다라고 생각했다.

[최대가 될 수 있는 경우]

1. 꿀벌중 한마리 왼쪽 고정 + 꿀통 오른쪽 고정 후 꿀벌 2의 위치 [1,n-1]까지 바꾸면서 최댓값을 찾는다.
   • [1,n-1] 위치에서 최대한 작은 값을 왼쪽 고정된 꿀벌의 누적합을 작게 감소시킬수 있기 때문이다.
2. 꿀벌 중 한마리 오른쪽 고정 + 꿀통 왼쪽 고정후 꿀벌 2의 위치 [1,n-1]까지 바꾸면서 최댓값
   • 위와 같은 이유이다.
3. 꿀벌 양쪽 고정 배치, 꿀통을 이동시킨다. [예외 케이스]
   • 예제에 나와있는듯이 n=3일 때, 꿀 1번 케이스 또는 2번 케이스 경우 첫값 또는 끝값이 최대가 된다. 혹여나 [1,100,3] 인 경우 200이 최대가 되기 때문이다.

public static void main(String[] args) {
		Reader reader = new Reader();
		int n = reader.n;
		int[] honies = reader.arr;

		// 어떻게 하면 최대 꿀을 딸 수 있을까?
		// - 조합 완전 탐색 x -> 시간초과
		// 누적합도 아니고.. -> 최적의 경우를 뽑아내는게 힘들었네..
		int rightSum[] = new int[n];
		int leftSum[] = new int[n];

		rightSum[0] = honies[0];
		leftSum[n - 1] = honies[n - 1];

		for (int i = 1; i < n; i++) {
			rightSum[i] = rightSum[i - 1] + honies[i];
		}

		for (int i = n - 2; i >= 0; i--) {
			leftSum[i] = leftSum[i + 1] + honies[i];
		}

		int answer = 0;

		// 꿀벌 1 -> [꿀벌1 위치 +1, 벌통위치]
		int bee1Total = (rightSum[n - 1] - honies[0]);

		//1.벌통 오른쪽 고정 , 꿀벌 1 한마리 왼쪽 고정
		for (int i = 1; i < n - 1; i++) {
			int bee1 = bee1Total - honies[i];
			int bee2 = leftSum[i] - honies[i];

			answer = Math.max(answer, bee1 + bee2);
		}

		// 꿀벌 1 -> [꿀벌1 위치 -1, 0]
		bee1Total = (leftSum[0] - honies[n - 1]);

		//2. 벌통 왼쪽 고정, 꿀벌1 한마리 오른쪽 고정
		for (int i = 1; i < n - 1; i++) {
			int bee1 = bee1Total - honies[i];
			int bee2 = rightSum[i] - honies[i];

			answer = Math.max(answer, bee1 + bee2);
		}

		//3. 왼쪽,오른쪽 벌 1,2, 고정 벌통 이동
		for (int i = 1; i < n - 1; i++) {
			int bee1 = rightSum[i] - honies[0];
			int bee2 = leftSum[i] - honies[n - 1];

			answer = Math.max(answer, bee1 + bee2);
		}

		print(String.valueOf(answer));
	}

	public static void print(String s) {
		System.out.println(s);
	}

	static class Reader {
		Scanner sc = new Scanner(System.in);
		int n;
		int[] arr;

		public Reader() {
			n = parse(sc.nextLine());

			arr = new int[n];
			StringTokenizer st = new StringTokenizer(sc.nextLine());
			for (int i = 0; i < n; i++) {
				arr[i] = parse(st.nextToken());
			}
		}

		public static int parse(String s) {
			return Integer.parseInt(s);
		}

	}