[DP] 2579번 계단오르기

"이것이 코딩테스트다(나동빈 저)"에서 나온 문제에 대한 코드를 다루고 있습니다.
문제에 대한 구체적인 설명과 조건 등은 책을 참고해주시기 바랍니다.

소요시간: 30분 + a

1. 문제 설명

- https://www.acmicpc.net/problem/2579

2579번: 계단 오르기

2. 접근 방식

- 마지막 계단이 밟혀있다고 가정하고 시작한다. (뒤에서부터 시작)
- 그 전의 계단은 End-1이거나, 맨 마지막 End-2일 것이다.

- End를 End-1에서 왔을 경우(한 칸), "End + End-1 + dp[end-3]" 과 같은 점화식이 된다.
- End를 End-2에서 왔을 경우(두 칸), "End + dp[end-2]"와 같은 점화식이 만들어진다.

- 해당 문제는 End를 꼭 밟아야 되기 때문에 End부터 점화식을 세운다.

+ 1일 때, 별도의 조건을 설정해줘야 한다.

3. 코드

# import sys
# input = sys.stdin.readline

n = int(input())
ls = [0]
for _ in range(n):
    ls.append(int(input()))

dp = [0] * (n+1)
dp[1] = ls[1]
if n!= 1:
    dp[2] = max(ls[2], dp[1]+ls[2])
    for i in range(3, n+1): # 3에서 N까지 간다
        dp[i] = max((ls[i]+ls[i-1]+dp[i-3]), (ls[i]+dp[i-2]))
print(dp[n]

4. 코멘트

- - 점화식을 세우고 나면, dp에 미리 값을 넣어야 하는 초기값을 세팅할 수 있다.