테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.

====== blobnom ======

===== 풀이 =====
  * i번째 탑을 가장 높게 만들수 있는 방법은, i-1번째 탑이나 i+1번째 탑의 높이가 0이 될때까지 i번째 탑을 선택하는 것이고, 그때의 최대 높이는 x[i] + min(x[i-1], x[i+1])가 된다.
  * 그 외에 다른 탑을 선택해봤자 더 높아지게 만들수 있는 방법은 없다. i-1번째 탑을 높인 다음에 그것을 i번째 탑으로 몰아주려고 생각해봐도, i-1번째 탑을 높이려면 i번째 탑이 낮아지기 때문에 효과가 없다.
  * 따라서 답은 max(x[i] + min(x[i-1], x[i+1])) 가 된다. 이것은 O(n) 에 계산 가능.
  * 그리고 실수하기 쉬운 부분이, 첫번째나 마지막 탑이 가장 높을 수도 있다. 따라서 진짜 답은 위에서 구한값과 x[0], x[-1]을 같이 비교해줘서 계산하면 된다.

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 24498. blobnom".

- Problem link: https://www.acmicpc.net/problem/24498
- Solution link: http://www.teferi.net/ps/problems/boj/24498

Tags: [Ad Hoc]
"""


def main():
    N = int(input())  # pylint: disable=unused-variable
    A = [int(x) for x in input().split()]

    answer = max((y + min(x, z) for x, y, z in zip(A, A[1:], A[2:])), default=0)
    answer = max(answer, A[0], A[-1])
    print(answer)


if __name__ == '__main__':
    main()
</dkpr>

{{tag>BOJ ps:problems:boj:실버_4}}