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()
ps/problems/boj/24498.txt · 마지막으로 수정됨: 2022/02/28 14:02 저자 teferi
토론