[boj21758/Java] 꿀 따기

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

21758번: 꿀 따기

이 문제에서 탐색을 통해서 구할 수 있는 최대의 꿀 양을 찾기 위해서 꿀벌1, 꿀벌2, 벌통을 움직여야 한다.

벌통과 꿀벌의 위치 관계에 따라서 꿀벌의 이동 방향이 달라지는데

벌통, 꿀벌1, 꿀벌2를 모두 이동시키려면 반복문을 3중으로 써야하고 탐색할 필요 없는 경우까지 탐색해야하므로

최대한 반복문의 사용을 줄이기 위해서 케이스를 3개로 나눠서

1. 벌통이 오른쪽 끝에 고정되어 있는 경우

- 벌 두마리가 전부 벌통보다 왼쪽에 있는 경우 제일 많은 양의 벌꿀을 모으기 위해서는

벌통이 가장 오른쪽에 있어야 하고 한마리의 벌은 가장 왼쪽에 고정되어 있어야 한다.

-> 그러면 나머지 한마리만 움직이면서 벌꿀 양 최댓값을 찾으면 됨

2. 벌통이 왼쪽 끝에 고정되어 있는 경우

- 벌 두마리가 전부다 벌통보다 오른쪽에 있는 경우 제일 많은 양의 벌꿀을 모으기 위해서는

벌통이 가장 왼쪽에 있어야하고 한마리의 벌은 가장 오른쪽에 고정되어 있어야 한다.

-> 1번과 마찬가지로 나머지 한마리만 움직이면 됨

3. 벌-벌통-벌 의 위치로 배치된 경우

- 벌은 모두 양 끝에 고정시키고 벌통을 움직이면서 최댓값을 구하기

 

이렇게 해결할 수 있다.

각각의 경우 해결법을 좀 더 자세히 생각해보면

1. 한마리의 벌을 움직이면서 합을 구할 때

- 고정되어 있는 벌이 모을 수 있는 꿀의 양은 전체 꿀 - 자기 위치 - 다른 벌의 위치 이다.

-> 고정되어 있는 벌의 고정된 값은 전체꿀 - 자기위치이므로 여기까지만 저장해두고 다른 벌의 위치는 그때그때 달라지기 때문에 탐색하면서 sum에서 계산하는걸로 한다.

- 움직이는 벌이 모을 수 있는 꿀은 고정된 벌이 모을 수 있는 꿀의 양에서 칸을 오른 쪽으로 옮기면서

한칸씩 꿀의 양을 줄여가면 된다.

그리고 최댓값을 비교해가면서 탐색한다!

 

2의 경우는 1과 같으나 방향이 오른쪽에서 왼쪽이다.

 

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

- 왼쪽 끝에 있는 벌에 탐색과 함께 1번 칸부터(0번칸은 벌이 있어서 못넣음) 꿀의 양을 한칸씩 넣어줌

- 오른쪽 끝에 있는 벌은 전체에서 length-1번칸을 제외하고 점점 꿀의 양을 줄여가면서

최댓값을 찾으면 됨!

 

그래서 결과적으로 코드는 다음과 같다.

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

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int N = Integer.parseInt(br.readLine());
		long[] honey = new long[N];
		long totalHoney = 0;
		st = new StringTokenizer(br.readLine());
		
		for(int i = 0; i<N; i++) {
			honey[i] = Long.parseLong(st.nextToken());
			totalHoney += honey[i];
		}
		
		long maxHoney = 0;
		
		long fixBee = totalHoney - honey[0];
		long moveBee = fixBee;
		
		for(int i = 1; i < honey.length -1; i++) {
			long sum = fixBee - honey[i];
			moveBee = moveBee - honey[i];
			sum += moveBee;
			maxHoney = Math.max(sum, maxHoney);
		}
		
		
		fixBee = fixBee + honey[0] - honey[honey.length -1];
		moveBee = fixBee;
	
		for(int i = honey.length - 2; i >= 0; i--) {
			long sum = fixBee - honey[i];
			moveBee = moveBee - honey[i];
			sum += moveBee;
			maxHoney = Math.max(sum, maxHoney);
		}
		
		fixBee = 0;
		moveBee = totalHoney - honey[honey.length -1];
		
		for(int i = 1; i < honey.length -1; i++) {
			long sum = 0;
			fixBee += honey[i];
			moveBee = moveBee - honey[i-1];
			sum = moveBee + fixBee;
			maxHoney = Math.max(sum, maxHoney);
		}
		
		System.out.println(maxHoney);
	}

}