[백준 2579 계단 오르기 문제] PYTHON

 

이전의 RGB 문제와 비슷한 유형이다.

다른 점을 꼽으면 이차원 배열로 만들어진 dp가 아니라 1차원이고

RGB는 전 집의 색들로 min값을 찾아 dp를 구성했고

이 계단 오르기 문제는 전,2개전,3개전 집의 선택 여부로 dp를 구성한다

 

현재 집 i 로서는 dp[i-2]+cost[i-1]+cost[i] 아니면 dp[i-2]+cost[i] 두가지 경우밖에 없다.

여기서 dp란 해당 집이 선택됐을때의 점수 최대 값을 의미한다.

 

N = int(input())
cost= []
dp = [0 for i in range(301)]
for _ in range(N):
    cost.append(int(input()))

if(N==1):
    print(cost[0])
elif(N==2):
    print(cost[0]+cost[1])
elif(N==3):
    print(max(cost[0]+cost[2],cost[1]+cost[2]))
else:
    dp[0]=cost[0]
    dp[1]=cost[0]+cost[1]
    dp[2]=max(cost[0]+cost[2],cost[1]+cost[2])
    for i in range(3,N):
        dp[i]=max(dp[i-3]+cost[i]+cost[i-1],dp[i-2]+cost[i])
    print(dp[N-1])

 

 

계속 인덱스 에러가 나와서 if문으로 1,2,3의 경우를 처리했다.