[백준/BOJ] 21758번 꿀 따기 자바 풀이

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

21758번: 꿀 따기

 

 

각 장소에서 딸 수 있는 꿀의 양이 입력으로 주어진다.

벌은 벌통까지 직선으로 이동하며 꿀을 딸 수 있다.

벌 두 마리와 벌통의 위치를 적절하게 정하여 벌들이 딸 수 있는 최대의 꿀의 양을 출력하는 문제다.

 

그리디 알고리즘을 사용하는 문제다.

N의 최대가 100000이므로 선형 시간이 들도록 알고리즘을 짜야 한다.

 

 

조금 복잡하게 푼 것 같지만..

먼저 세가지의 경우로 나눌 수 있다.

1) 벌통이 가장 오른쪽에 위치하는 경우

2) 벌통이 중간에 위치하는 경우

3) 벌통이 가장 왼쪽에 위치하는 경우

 

 

1)번의 경우 꿀의 양이 최대가 되려면 첫 번째 벌은 벌통과 가장 멀리, 즉 가장 왼쪽에 위치해야 한다.

벌 _ _ _ _ _ ... _ _ 벌통

따라서 위와 같은 상태에서 중간에 있는 벌 하나를 더 구하면 된다.

이 때 첫 번째 벌은 (모든 꿀의 합) - (자신의 위치에 있는 꿀의 양) - (두 번째 벌의 위치에 있는 꿀의 양) 만큼 꿀을 딸 수 있다.

벌통이 있는 가장 오른쪽으로 이동하면서 꿀을 따고, 중간에 두 번째 벌을 만나면 그 꿀은 딸 수 없기 때문이다.

 

두 번째 벌의 위치를 구하기 위해

왼쪽에서 오른쪽으로 이동하면서 그 위치를 (i번째) 두 번째 벌이라고 가정한다.

두 번째 벌은 첫 번째 벌의 꿀 양에서 자신의 위치 전까지의 꿀 양을 뺀 만큼 꿀을 딸 수 있다.

예를 들어 3번째가 두번째 벌이라면, 첫번째 벌의 꿀 양에서 1, 2번째 꿀의 양을 뺀 값과 같다.

즉, 두 번째 벌의 꿀 양은 누적하면서 자신의 위치에 있는 꿀만 빼주면 된다. 

 

이렇게 왼쪽에서 오른쪽까지 두 번째 벌의 꿀 양을 구해가면서

answer를 갱신해나간다.

 

 

2)번의 경우 양 끝에 벌을 위치한 경우가 무조건 최대가 된다.

가장 끝 값을 제외한 모든 값이 중간에 있는 벌통이 될 수 있으므로

1번째부터 N-2번째까지 벌통임을 가정하고 그때의 꿀 양을 구하면된다.

벌 _ _ _ 벌통 _ _ _ 벌

위와 같을 때 왼쪽 벌은 1번째부터 벌통까지의 꿀의 합, 오른쪽 벌은 N-1번째부터 벌통까지의 꿀의 합을 딸 수 있다.

이를 더해주면 (모든 꿀의 합 + 벌통 위치의 꿀 - 왼쪽 벌 위치의 꿀 - 오른쪽 벌 위치의 꿀)이 된다.

 

 

3)번의 경우 꿀의 양이 최대가 되려면 첫 번째 벌은 벌통과 가장 멀리, 즉 가장 오른쪽에 위치해야 한다.

1)번의 경우와 동일하게 누적해서 꿀의 양을 빼가면서 answer를 갱신해나가면 된다.

이때는 왼쪽부터 오른쪽이 아닌 오른쪽부터 왼쪽으로 벌이 이동하므로

for문의 조건이 바뀌는 것을 주의하면 된다.

 

 

 

전체 코드

import java.util.*;
import java.io.*;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int[] honey = new int[N];

		int answer = 0;
		int first, second, middle;
		int sum = 0;
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=0;i<N;i++) {
			honey[i] = Integer.parseInt(st.nextToken());
			sum += honey[i];
		}

		first = sum - honey[0]; // 가장 왼쪽 벌이 딴 꿀의 양 (가장 오른쪽이 벌통인 경우 첫 번째 벌은 왼쪽 벌으로 고정)
		second = first;
		middle = sum - honey[0] - honey[N - 1]; // 중간에 벌통이 존재하는 경우 -> 전체 합에서 양끝 빼고 중간값 더하기

		for(int i=1;i<N-1;i++) {
			// 중간에 벌통이 존재하는 경우 
			answer = Math.max(middle + honey[i], answer);

			// 가장 오른쪽이 벌통
			first -= honey[i]; // i가 두 번째 벌인 경우, 그 장소의 꿀 제외
			second -= honey[i];
			answer = Math.max(first + second, answer);
			first += honey[i]; // 다시 되돌리기 (두 번째 벌은 왼쪽으로 한 칸씩 이동하면서 꿀의 양이 줄어드므로 되돌리지 않음)
		}

		first = sum - honey[N - 1]; // 가장 오른쪽 벌이 딴 꿀의 양 (가장 왼쪽이 벌통인 경우 첫 번째 벌은 오른쪽 벌으로 고정)
		second = first;

		for(int i=N-2;i>0;i--) {
			// 가장 왼쪽이 벌통
			first -= honey[i]; // i가 두 번째 벌인 경우, 그 장소의 꿀 제외
			second -= honey[i];
			answer = Math.max(first + second, answer);
			first += honey[i]; // 다시 되돌리기 (두 번째 벌은 왼쪽으로 한 칸씩 이동하면서 꿀의 양이 줄어드므로 되돌리지 않음)
		}

		System.out.println(answer);
	}

}