백준 2579 계단 오르기

유형 : dp

 

문제풀이

 포도주 시식 문제와 유사하지만, 마지막 계단을 반드시 밟아야한다는 제한이 있다. 

 따라서 i번째 계단의 점수가 s[i]라 하면, i번째 계단을 밟았을 때의 최대 점수 dp[i]는 다음과 같이 주어진다.

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

 즉, 2칸 전 계단을 밟고 이번 계단을 밟거나, 3칸 전 계단을 밟고 전칸을 밟고 이번 계단을 밟거나 두가지 조건이 가능하다.

 

list 초기화와 append

 위의 문제를 해결하는데 있어서, dp를 먼저 빈 list로 선언한 후 append로 하나씩 채워갈 수도 있고, dp를 길이가 n인 리스트로 선언한 후, i번째 요소를 바꿔가는 방법이 있는데, 후자가 효율적이다. 전자로 통과한 후, 후자의 방법으로 바꾸었더니 80ms 에서 56ms로 줄었다.

 

Python Code

import sys
n = int(sys.stdin.readline())
s = [0 for i in range(n)]
dp = [0 for i in range(n)]
 
for i in range(min(3,n)):
    s[i]=int(sys.stdin.readline())
if n>3:
    dp[0]=s[0]
    dp[1]=s[0]+s[1]
    dp[2]=max(s[0]+s[2],s[1]+s[2])
    for i in range(3,n):
        s[i] = int(sys.stdin.readline())
        dp[i]=max(dp[i-2]+s[i],dp[i-3]+s[i-1]+s[i])
elif n==3:
    dp=[s[0],s[0]+s[1],max(s[0]+s[2],s[1]+s[2])]
else:
    dp=[sum(s)]
print(dp[-1])