백준 2579: 계단 오르기 ( Dynamic Programming / with C )

계단을 오르는 규칙을 어떻게 코드에 적용하는지가 중요한 문제였다.

먼저, 각 계단 칸에  할당된 값을 data[] 배열에 저장하고,

각 칸을 밟을 경우 획득할 수 있는 최댓값(맨 앞에서부터 해당 칸까지 도달하면서 얻을 수 있는 최댓값)을 result[] 배열에 담았다.

 

DP에서는 항상 새로운 항의 값을 만들 때, 겹치는 것이 없도록 앞의 값들에서 확장하는 것이 중요하다.

1. 바로 전 칸을 밟고 현재 계산중인 칸으로 넘어가는 경우

=> 이 경우에는 현재 계산중인 칸의 전전 칸을 밟으면 안된다(3개 연속 밟게 되는 것이므로). 따라서 3개 전 칸의 최대치에 전 칸의 값을 더한 것 ( result[i-3] + data[i-1] )

 

2. 전전 칸을 밟고, 바로 전 칸은 밟지 않고 현재 계산중인 칸으로 넘어가는 경우 

=> 전전칸의 최대치 ( result[i-2] )

 

이 두가지 중 큰 값을 data[i]와 더해서 result[i]에 할당하면 된다.