백준 - 2579번: 계단 오르기 - 파이썬

백준 - 2579번: 계단 오르기

문제

입출력 형식 및 출처

length = int(input())
score = [0]*300

for i in range(length):
    score[i] = int(input())

dp = [0]*300
dp[0] = score[0]
dp[1] = max(score[0]+score[1], score[1])
dp[2] = max(score[0]+score[2], score[1]+score[2])

for i in range(3, length):
    dp[i] = max(score[i]+dp[i-2], score[i]+score[i-1]+dp[i-3])

print(dp[length-1])

동적프로그래밍(Dynamic Programming) 문제

• 밟는 계단의 점수가 주어질 때 이의 최대값을 구현하는 문제
• 계단을 연달아 3개를 밟을 수 없다는 조건이 주어진다
• 내가 밟은 계단의 위치에서 -1칸과 -2칸의 값을 더한 후 비교하여 최대값을 dp리스트에 저장해준다!
• 최종적으로 구해진 dp리스트의 마지막 값을 출력