[백준] C++ 21758(꿀 따기)

백준/그리디

[백준] C++ 21758(꿀 따기)

2zreal 2024. 7. 7. 05:22

#include <iostream>

using namespace std;

int arr[100001];

int main(void)
{
	int N=0;
	cin>>N;
	
	for(int i=0; i<N; i++)
	{
		cin>>arr[i];
	}
	
	for(int i=1; i<N; i++)
	{
		arr[i]=arr[i]+arr[i-1];
	}
	
	
	//right
	int result=(arr[N-1]-arr[0]) + (arr[N-1]-arr[1]) - (arr[1]-arr[0]);
	int i=2;
	while(true)
	{
		if(i>N-2)
		{
			break;
		}
		int temp=(arr[N-1]-arr[0]) + (arr[N-1]-arr[i]) - (arr[i]-arr[i-1]);
		if(result<temp)
		{
			result=temp;
		}
		
		i++;
	}
	
	//left
	int result2=(arr[N-2]) + (arr[N-3]) - (arr[N-2]-arr[N-3]);
	int j=4;
	while(true)
	{
		if(j>=N)
		{
			break;
		}
		int temp=(arr[N-2]) + (arr[N-j]) - (arr[N-j+1]-arr[N-j]);
		if(result2<temp)
		{
			result2=temp;
		}
		
		j++;
	}
	
	//middle
	
	int result3=(arr[1]-arr[0]) + (arr[N-2]-arr[0]);
	int l=2;
	while(true)
	{
		if(j>=N)
		{
			break;
		}
		int temp=(arr[l]-arr[0]) + (arr[N-2]-arr[l-1]);
		if(result3<temp)
		{
			result3=temp;
		}
		
		l++;
	}
	
	int max=0;
	
	if(max<result)
	{
		max=result;
	}
	if(max<result2)
	{
		max=result2;
	}
	if(max<result3)
	{
		max=result3;
	}
	cout<<max;

	
	return 0;
}

꿀벌 2마리가 꿀통으로 똑바로 날아가면서 얻은 꿀의 최댓값을 구하는 문제이다.

꿀벌은 서로 다른 위치에 존재하고 꿀통도 꿀벌과 서로 다른 위치에 존재한다.

꿀벌은 자기가 시작하는 위치의 꿀을 얻지 못한다.(최댓값을 구하기 위해 고려해야 할 주요 조건)

이 문제를 어떻게 접근해야 하는가??

for(꿀통) for(꿀벌 1) for(꿀벌 2) 3중 for문을 사용한다면?

이 문제를 for문을 3번 사용해서 풀게 되면 분명 시간초과가 발생할 것이다. 입력값으로 100,000까지 올 수 있기 때문이다.

그러면 어떤 방법으로 접근해야 하는가??

문제의 정확하게 이해해야 한다.

꿀통을 기준을 생각해 보자. 꿀통이 만약 맨 오른쪽에 위치한다면 꿀벌들은 맨 왼쪽에서 시작해야 할 것이다. 만약 꿀벌이 맨 왼쪽이 아니고 한 칸이라도 떨어진 곳에서 시작한다면 최댓값을 구하지 못한다.