사용자 도구

사이트 도구


ps:problems:boj:24498

blobnom

ps
링크acmicpc.net/…
출처BOJ
문제 번호24498
문제명blobnom
레벨실버 4
분류

애드혹

시간복잡도O(n)
인풋사이즈n<=10^6
사용한 언어Python
제출기록156756KB / 664ms
최고기록664ms
해결날짜2022/02/28

풀이

  • 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]을 같이 비교해줘서 계산하면 된다.

코드

"""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()

토론

댓글을 입력하세요:
H O B O Z
 
ps/problems/boj/24498.txt · 마지막으로 수정됨: 2022/02/28 14:02 저자 teferi