1. 마지막 계단 말고 첫번째 계단도 항상 밟아야 하나요?

2. 밑에 코드는 첫번째 계단도 항상 밟는다고 가정하고 작성한 코드입니다. 값은 제대로 나오는 데 반례가 있을까요? 접근 방식이 잘못된 걸까요?

(접근방식)

주어진 조건을 보고 n이 짝수일 때와 홀수일 때 다르게 처리해야 한다 판단했습니다.

기본적인 접근방식은 이렇습니다.

a0 a1 a2 a3 a4 a5 a6 ... 이런 식으로 진행할 때 세개의 계단은 연속해서 못 밟고, 세 계단 점프는 안 되기 때문에 a1 a2 | a3 a4 | a5 a6| 이렇게 두개씩 끊어서 두 수 중 큰 수를 택합니다. 이렇게 하면 주어진 조건을 만족시키면서도 큰 숫자들을 고르게 되니 최대값이 될 거라고 판단했습니다.

하지만 n이 홀수일 때는 상황이 좀 달라집니다. 예를들어 10 | 15 20 | 25 10 이라면 앞서 말했던 방식에 의해 20 25 10 이렇게 세 계단을 연속해서 밟게 됩니다. 그래서 n이 홀수일 경우에는 마지막 계단과 그 앞 계단 세개를 포함해서 총 4개의 계단은 따로 처리했습니다. 그니까 20 25는 동시에 선택할 수 없으니까 15+25 와 20의 크기를 비교해서 더 큰 수를 dp에 append 해줬습니다.

dp.append(max(lst[n-4]+lst[n-2]+lst[n-1], lst[n-3]+lst[n-1]))