[dp/백준] 2579번: 계단 오르기

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

 

-정답풀이

• i-1번째 계단에서 온 경우. 이때는 i-3 -> i-1 ->i 의 루트를 거쳐야 한다. 이유는 한칸씩 연속으로 3번 오는 거를 피하기 위해서다
• i-2번째 계단에서 온 경우 이미 한칸씩 연속 세번 올 경우는 없으므로 i-2 -> i 의 루트를 생각하면 된다

위 과정을 기반으로 코드를 작성하면 다음과 같다 

n=int(input())
data=[0]
for _ in range(n):
    data.append(int(input()))
if n==1: #이거를 빼면 indexError가 발생한다
    print(data[1])
else:    
    dp=[0]*(n+1)    
    dp[1]=data[1]
    dp[2]=data[2]+data[1]

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

 

-삽질 기록

이전에 풀었던 기억으로 i번째 계단으로 올라왔다면 두가지 경우가 있다 

• i-1번째 계단에서 온 경우. 이때는 i-3 -> i-1 ->i 의 루트를 거쳐야 한다. 이유는 한칸씩 연속으로 3번 오는 거를 피하기 위해서다
• i-2번째 계단에서 온 경우 i-3 -> i-2 -> i의 경로를 생각했다. 근데 굳이 그럴 필요가 없이 i-2 -> i 경로만 생각하면 된다 

나름 점화식 생각한다고 했는데 오류가 많다 

data[i]= data[i-3] + max(data[i-1],data[i-2]) # 잘못된 점화식
dp[i]= data[i]+max(dp[i-3]+data[i-1],dp[i-2]) #이걸로 고쳐야함