[백준] 2579번 : 계단 오르기 (파이썬)

문제

나의 답안

n=int(input())
floor=[0 for i in range(301)]#층의 가중치 저장
dp=[0 for i in range(301)]#가중치 합 저장

for i in range(n):
    floor[i]=int(input())#입력받은 값 저장

dp[0]=floor[0]#첫번째 계단까지의 합
dp[1]=floor[0]+floor[1]#두번째 계단까지의 합
dp[2]=max(floor[0]+floor[2],floor[1]+floor[2])
#큰 값 고르기, max(두칸 올라가기, 한칸 올라가기)

for i in range(3,n):
    dp[i]=max(dp[i-2]+floor[i],dp[i-3]+floor[i]+floor[i-1])
    #현재까지의 가중치=(2칸 전까지의 가중치 합+현재 가중치,
    #3칸 전 가중치의 합+현재 가중치+한칸 전 계단의 가중치)
    
print(dp[n-1])

접근 방법

• dp문제이므로 계단의 수만큼 미리 초기화를 해주었다.
• 마지막 칸은 반드시 밟아야 하므로 시작을 고려하는 것이 아니라 뒤쪽 계단에서 어떻게 올라왔는지 고려하면 된다.
• 1칸, 2칸씩 오를 수 있으나 연속해서 3칸은 불가하므로
  현재까지의 가중치 = max(2칸 전까지의 가중치 합+현재 가중치, 3칸 전 가중치의 합+현재 가중치+한칸 전 계단의 가중치) 로 구해주면 된다.
• 첫번째 계단의 인덱스를 0으로 설정해주고 문제를 풀었다.