선택한 원소의 인접한 원소는 선택할 수 없을 때 원소 합을 최대로 선택하는 방법

7265번: Herbamedžiai (acmicpc.net)  배열에서 i번째 원소를 선택하면 i-1번째, i+1번째 원소는 선택할 수 없을때, 선택할 수 있는 원소의 최대 합을 구한다면 n이 최대 10만이라 O(N)에는 해결해줘야한다 $O(N^{2})$ 아니면 못할것 같지만 놀랍게도 O(N)에 되더라고 DP[i] = i번째 원소까지 봤을때 선택한 원소들의 최대합 만약 i번째 원소를 선택하지 않는다면? dp[i] = dp[i-1]로 그대로 가져오면 된다 만약 i번째 원소를 선택한다면? i-1번째 원소는 선택할 수 없으므로, dp[i-2]에다가 i번째 원소 선택 A[i]를 더해주면 된다 dp[i] = dp[i-2] + A[i] 여기서 둘 중 더 큰 값을 고르면 된다 dp[i] = max(dp[i-1], d..