[백준] 21758 - 꿀 따기 (JAVA)

개츠비·2023년 4월 25일

백준

목록 보기

62/84

소요시간 : 1시간
문제 사이트 : 백준
문제 수준 : 골드 5
문제 유형 : 그리디 알고리즘, 누적 합, 많은 조건 분기
다른 사람의 풀이를 참고 했는가 ? : X
한 번 풀었다가 다시 푸는 문제인가 ? : X
문제 링크 : https://www.acmicpc.net/problem/21758
푼 날짜 : 2023.04.25

1. 사용한 자료구조 & 알고리즘

그리디 알고리즘, 누적합을 사용

2. 사고과정

N이 100,000 까지이므로 O(N^2) 으로는 풀 수 없을 것으로 생각. O(N^2) 이라면 이중 for문으로 모든 경우의 수를 체크하는 간단한 방법으로 해결할 수 있었을 것이다.

10분쯤 경과했을 때 누적합으로 풀 수 있을 것으로 생각했고,
어떤 조건으로 벌집과 벌의 위치를 조절해야하는지를 가장 많이 고민했다.

고민한 결과는 우선 이 문제를 3가지 경우의 수로 나누어 보는 것이다.
벌 - 벌 - 벌집
벌 - 벌집 - 벌
벌집 - 벌 - 벌
의 3가지 경우의 수가 나올 수 있고,
각각에 대해서 따로 누적합을 계산해줌으로써
가장 큰 값을 출력하면 된다는 결론을 내렸다.

가운데에 벌집이 있는 경우는 비교적 쉬웠으나,
벌 - 벌 - 벌집 과 벌집 - 벌 - 벌 은 어떻게 벌의 위치를 조절해줘야 되는지를 계속 고민함. 처음에는 무조건 벌을 가장 왼쪽에 2마리 배치시키는 쪽으로 생각했는데 문제의 예시만 봐도 그것이 답이 아님을 알 수 있었다. 여기서 누적합을 응용해서
우선 벌 1마리는 가장 끝에 배치 시키고 , 그 후에 O(N) 으로 계속 누적합을 비교해가면서 어떤 경우가 가장 많은지 계산하는 방법으로 문제를 해결했다.

3가지 모두 각각의 경우에 대해서는 누적합을 구하는 데에도 O(N) 이고, 누적합을 구한 후에도 각각의 경우에 대해서 벌의 위치를 조절하는데에도 O(N) 이므로 총 시간복잡도는 O(N) 이 걸림.

3. 풀이과정

3가지 테스트케이스로 나눠서 봄.
벌집이 가운데에 있지 않은 경우에는 무조건 왼쪽 끝 혹은 오른쪽 끝에 배치함. 마찬가지로 벌 또한 한마리는 무조건 반대방향의 맨 끝에 배치함.
두 번째 벌은 O(N)으로 각각의 위치에서의 합을 계산해줌으로써 2번째 벌의 위치를 계산함.
벌집이 가운데에 있는 경우는 벌이 무조건 양쪽 끝에 놓일 수밖에 없음. 벌집의 위치는 마찬가지로 O(N) 으로 모든 경우의 수에서의 누적합을 계산함.
3가지 경우의 수에서의 최댓값을 출력함

4. 소스코드

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

public class Main{

	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=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 rightHoney() { //벌통이 왼쪽에 위치
		
		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 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;
	}
}