Boj 21758 c++ 꿀따기

또다시 찾아온 그리디

풀이시간 약 1시간 30분

 

이번 문제의 핵심은 경우를 나누어서 풀기. 너무 어렵게 생각하면 안된다. '어떻게 해야 최적이 될까?'에 대한 해답은 생각보다 가까이 있다.

 

벌 - 벌 - 꿀통

벌 - 꿀통 - 벌 

꿀통 - 벌 - 벌

 

3가지 경우로 나누어서 풀어야 한다.

#include<iostream>
#include<vector>

using namespace std;

long long dp[100001];//누적합

int main(){
  ios_base :: sync_with_stdio(false);
  cin.tie(NULL);

  int N;
  long long bee1=0, bee2=0, ans=0;

  cin>>N;
  vector<int> v(N);


  for(int i=0; i<N; i++){
    cin>>v[i];

  }
  for(int i=1; i<N; i++){
    dp[i]=dp[i-1]+v[i];
  }

  for(int i=N-2; i>0; i--){
    bee1=dp[N-2]+v[0]-v[i];
    bee2=dp[i-1]+v[0];
    ans=max(ans, bee1+bee2);
  }
  for(int i=1; i<N-1; i++){
    bee1=dp[i];
    bee2=dp[N-2]-dp[i-1];
    ans=max(ans, bee1+bee2);
  }
  for(int i=1; i<N-1; i++){
    bee1=dp[N-1]-v[i];
    bee2=dp[N-1]-dp[i];
    ans=max(ans, bee1+bee2);
  }
  cout<<ans;


}