백준 BOJ 21758 - 꿀 따기

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

21758번: 꿀 따기

부분합 + 그리디 문제.

꿀벌 둘을 A,B ( B가 더 오른쪽에 있는 꿀벌 )

벌통을 C로 두면

크게 세가지 경우의 수가 있을 수 있다.

 

1. A < B < C 순 배치.

이 경우에 있어서, 꿀통인 C는 오른쪽 끝에 위치하는것이 가장 이득이 되고,

첫번째 꿀벌 A는 가장 왼쪽 끝에 위치하는것이 가장 이득이 된다.

남은 꿀벌 B가 어디에 있느냐에 따라서,

 

(전체 꿀 + B~C 이동에서의 꿀 - A, B지점에서의 꿀) 을 계산해주면 된다.

벌이 있는 곳에서는 꿀을 딸 수 없기 때문에 A, B 지점의 꿀은 계산에서 따로 빼줘야 함에 유의할것.

 

2. A < C < B 순 배치.

이 경우에 있어서, 꿀벌 둘은 각각 양쪽 끝에 있는 것이 가장 이득이 되므로,

남은 꿀통 C가 어디에 있느냐에 대해서

(A~C 이동에서의 꿀 + C~B 이동에서의 꿀 - A,B 지점에서의 꿀) 을 계산한다.

식정리를 좀 해보면

(전체 꿀 - A,B 지점에서의 꿀 + C 지점에서의 꿀) 을 계산하면 된다.

꿀통이 있는 지점인 C에 있는 꿀이 두번 더해짐에 유의할것.

 

3. C < A < B 순 배치.

두가지 구현법이 있는데,

(C~A 이동에서의 꿀 + 전체 - A,B 지점에서의 꿀) 을 계산하는 방법과

입력으로 들어온 배열을 뒤집어놓고 1번 경우에 따라 다시 계산해주는 방법이 있다.

나는 전자로 그냥 계산했다.

 

꿀을 더해주는것을 빠르게 계산하기 위해서 부분합 배열을 만들어주도록 하자.

전체 시간복잡도는 1,2,3 각각의 경우 모두 O(N) 이므로 O(N)

 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll arr[123456] = {0};
ll prf[123456] = {0};

int main(){
	cin.sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	int N;
	cin >> N;
	for(int i=1; i<=N; i++){
		cin >> arr[i];
		prf[i] = prf[i-1] + arr[i];
	}
	
	ll ans = -1;
	
	for(int i=2; i<N; i++){ // 벌통 오른쪽 끝.
		ans = max(ans, prf[N]*2-prf[1]-prf[i]-arr[i]);
	}
	
	for(int i=2; i<N; i++){ // 벌통 중간.
		ans = max(ans, prf[N]+arr[i] -arr[1] - arr[N]);
	}
	
	for(int i=2; i<N; i++){ // 벌통 왼쪽 끝. 
		ans = max(ans, prf[N]-arr[N]-arr[i] + prf[i]-arr[i]);
	}
	
	cout << ans;
	return 0;
}

범위가 int를 넘어갈 수 있으므로

long long 형으로 선언해준다.