#2579

 

 

재귀 -> 실패

연속으로 3개의 계단을 밟을 수 없다는 조건을 충족하기 위해서는 이전 상태를 저장해야 합니다. 따라서 dp로 방식을 바꿨습니다.

#input 받기
N =int(input())
numbers = [0] + [int(input()) for _ in range(N)]  # 1-indexed

#재귀
def recursive(k):
    if k ==1:
        return numbers[1]
    if k == 2:
        return numbers[1] + numbers[2]
    
    return numbers[k]+max(recursive(k-1), recursive(k-2))

print(recursive(N))

 

 

dp 정답

import sys

# 1. 입력 받기
N =int(input())
numbers = [0] + [int(input()) for _ in range(N)]  # 1-indexed


# 2. 예외 처리
if N == 1:
    print(numbers[1])
    exit()
if N == 2:
    print(numbers[1] + numbers[2])
    exit()

# 3. DP 테이블 초기화
dp = [0] * (N + 1)
dp[1] = numbers[1]
dp[2] = numbers[1] + numbers[2]
dp[3] = max(numbers[1] + numbers[3], numbers[2] + numbers[3])

# 4. 반복문: 반드시 4부터 시작해서 이미 채워진 1, 2, 3번을 보호해야 함
for i in range(4, N + 1):
    dp[i] = max(dp[i-2] + numbers[i], 
                dp[i-3] + numbers[i-1] + numbers[i])

# 5. 결과 출력
print(dp[N])