[BJ] 21758 : 꿀 따기

       문제 요약        

- 문제

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

 

 

         아이디어        

최대한 멀리 떨어뜨려놓고 시작

1) 벌(0) 꿀 벌(N-1)

2) 꿀(0) 벌 벌(N-1) 

3) 벌(0) 벌 꿀(N-1)

 

이렇게 3가지 경우에 대해 양 끝을 고정시킨 다음에

최대값 찾기

 

case2) case3) 의 경우 벌의 위치에 해당하는 꿀은 한 번 제외해줘야 함

 

 

         소스코드        

 

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

public class Main {
	static int N;
	static int[] box;

	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("src/input.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());

		StringTokenizer st = new StringTokenizer(br.readLine());
		box = new int[N];
		for (int i = 0; i < N; i++) {
			box[i] = Integer.parseInt(st.nextToken());
		}

		int[] left = new int[N];
		int[] right = new int[N];
		left[0] = box[0];
		right[N - 1] = box[N - 1];
		for (int i = 1; i < N; i++) {
			left[i] = left[i - 1] + box[i];
			right[N - 1 - i] = right[N - i] + box[N - 1 - i];
		}

		int max = 0;
		for (int i = 1; i < N - 1; i++) {
			// 벌(0) 꿀(i) 벌(N-1)
			max = Math.max(max, left[i] - left[0] + right[i] - right[N - 1]);
			// 벌(0) 벌(i) 꿀(N-1)
			max = Math.max(max, left[N - 1] - left[0] + left[N - 1] - left[i] - box[i]);
			// 꿀(0) 벌(N-1-i) 벌(N-1)
			max = Math.max(max, right[0] - right[N - 1] + right[0] - right[N - 1 - i] - box[N - 1 - i]);
		}
		System.out.println(max);

	}

}