[백준_2579] 계단오르기 python

실버3 문제라고 얕잡아봤다가 큰코다쳤다.

2칸전? 1칸전을 기준으로 이차원 배열로 생각하는 dp문제인가?하고 생각했는데,

생각보다 쉽지가 않았다.

결국 구글링을 통해 아이디어를 얻었다.

결론은 세칸 전과 두칸 전을 기준으로 나눠 큰 값을 취하는 dp점화식을 통해 해결하는 것이였다.

이게 어케 실3이야

# n 입력

n = int(input())

# 계단 값 입력용 리스트

stair = [

　0 for _ in range(301)

]

# 계단 값 입력

for i in range(1, n + 1):

　stair[i] = int(input())

# dp 설계

dp = [

　0 for _ in range(n + 1)

]

# n == 1

if n == 1:

　print(stair[1])

# n == 2

elif n == 2:

　print(stair[1] + stair[2])

# n == 3

elif n == 3:

　print(max(stair[1] + stair[3], stair[2], stair[3]))

# n >= 4

else:

　# 초기설정

　dp[1] = stair[1]

　dp[2] = stair[1] + stair[2]

　dp[3] = max(stair[1] + stair[3], stair[2] + stair[3])

　# dp 채워넣기　

　for i in range(4, n + 1):

　　dp[i] = max(dp[i-3] + stair[i-1] + stair[i], dp[i-2] + stair[i])

　# 출력

　print(dp[n])