한 번에 1칸 또는 2칸씩 앞으로 갈 수 있을 때 마지막 칸에 도착하며 얻을 수 있는 최대 점수를 출력하세요.
📥 테스트 입력값
5
1 10 30 100 30
🔎 실행 결과
171
💡 힌트 코치
뒤에서부터 DP를 채우거나 앞에서부터 누적해도 됩니다.
✅ 정답 공개
n = int(input())
scores = [int(x) for x in input().split()]
if n == 1:
print(scores[0])
else:
dp = [0] * n
dp[0] = scores[0]
dp[1] = scores[1] + max(0, dp[0])
for i in range(2, n):
dp[i] = scores[i] + max(dp[i - 1], dp[i - 2])
print(dp[-1])