백준 문제 24498번 blobnom 문제풀이 c++

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

24498번: blobnom

 

문제해석

 

이 문제에선 탑을 이것 저것 건드려봤자 이득이없다.

하나의 탑만 계속 선택하는것이 최대 탑의 높이가 된다.

탑은 양옆의 탑의 높이중 작은것만큼 선택 가능하기때문에 현재 탑 + 양옆의 탑높이중 작은것이 답이된다.

라고 생각하고 처음에 작성했던 코드가 틀렸다.

 

두번 틀리고나서 왜 틀린지 몰라서 알고리즘분류 열어봤는데 그리디 알고리즘이 맞는데 왜 틀렸는지 계속 모르다가

처음 탑과 마지막 탑은 선택이 불가능하니까 맨 처음 초기상태의 첫탑과 마지막 탑의 높이까지 비교를 해주어야 한다는 사실을 깨달았다.

 

코드

 

#include <iostream>
#include <algorithm>
typedef long long int ll;
using namespace std;
ll ans=0;
ll a[1000005];
int main(){
    cout.tie(NULL);
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    ll n;
    cin>>n;
    for(ll i=0; i<n; i++)
    {
        cin>>a[i];
    }
    for(ll i=1; i<n-1; i++)
    {
        ans=max(ans,a[i]+min(a[i-1],a[i+1]));
    }
    ans=max({a[0],a[n-1],ans});
    cout<<ans;
}