[알고리즘] 백준 2579 : 계단 오르기 - S3

2023.05.24 풀이

• 점화식 감이 잘 오지않았음

import sys
input=sys.stdin.readline

t=int(input())
arr=[0]*(301)
d=[0]*(301)
for i in range(t):
    arr[i]=int(input())

d[0]=arr[0]
d[1]=arr[0]+arr[1]
d[2]=max(arr[0]+arr[2], arr[1]+arr[2])
for i in range(3, t):
    d[i]=max(d[i-3]+arr[i-1]+arr[i], d[i-2]+arr[i])

print(d[t-1])

---

다른 풀이

n=int(input()) # 계단 개수
s=[int(input()) for _ in range(n)] # 계단 리스트
dp=[0]*(n) # dp 리스트
if len(s)<=2: # 계단이 2개 이하일땐 그냥 다 더해서 출력
    print(sum(s))
else: # 계단이 3개 이상일 때
    dp[0]=s[0] # 첫째 계단 수동 계산
    dp[1]=s[0]+s[1] # 둘째 계단까지 수동 계산
    for i in range(2,n): # 3번째 계단 부터 dp 점화식 이용해서 최대값 구하기
        dp[i]=max(dp[i-3]+s[i-1]+s[i], dp[i-2]+s[i])
    print(dp[-1])

---

check point

• 점화식 풀이 참고 1, 2
• 점화식을 잘 모르겠으면 끝에서 부터 내려오기/d[0]부터 바텀업으로 생각해보기
• 런타임에러 : d와 arr의 범위를 t에 관련해서 선언하지 않으면 런타임에러가 났음