[백준] 2579번 : 계단 오르기 with python3

12 Sep 2018

Reading time ~1 minute

문제 : https://www.acmicpc.net/problem/2579

import sys

n = int(sys.stdin.readline())
a = [int(sys.stdin.readline()) for i in range(n)]
a.insert(0,0)
d = [ [0]*3 for i in range(n+1)]

d[1][1] = a[1]
for i in range(2,n+1):
    d[i][2] = d[i-1][1] + a[i]
    d[i][1] = max(d[i-2][1], d[i-2][2]) + a[i]

print(max(d[n][2],d[n][1]))

d[i][1], d[i][2]는 1에는 한번 연속을 때 2는 두번 연속일 때 들어가는 수이다.

import sys

n = int(sys.stdin.readline())
a = [int(sys.stdin.readline()) for i in range(n)]
a.insert(0,0)
d = [0]*(n+1)

d[1] = a[1]
d[2] = a[1]+a[2]
for i in range(3,n+1):
    d[i] = max(d[i-2]+a[i], d[i-3]+a[i]+a[i-1])
print(d[n])

algorithm 백준