백준 2579번 계단 오르기

< 백준 2579번 계단 오르기 - 마포 코딩박 >

사용한 알고리즘: DP


 계단을 1칸, 혹은 2칸 오를 수 있고 연속된 3칸의 계단을 연속으로 밟아서는 안됩니다. 각 계단 칸을 밟을 때 해당 칸의 점수를 얻을 수 있습니다. 이때 마지막 칸에 도착했을 때 얻을 수 있는 최대 점수를 구하는 문제였습니다.

문제풀이는 다음과 같습니다.

(1) (코드 5~7)
 'dp[x][0] : 1칸 올라와서 x칸 도착했을 때 점수 최댓값' ,
 'dp[x][1] : 2칸 올라와서 x칸 도착했을 때 점수 최댓값' 으로 설정했습니다.

(2) (코드 12~15)
 dp[1][0] = A[1] : 1칸 올라와서 1계단에 도착했을 때 얻을 수 있는 점수 최댓값
 dp[2][0] = A[1]+A[2] : 1칸 올라와서 2계단에 도착했을 때 얻을 수 있는 점수 최댓값
 dp[2][1] = A[2] : 2칸 올라와서 2계단에 도착했을 때 얻을 수 있는 점수 최댓값
 위와같이 초기값을 설정합니다.

(3) (코드 17~20)
 초기값을 바탕으로 dp 값을 계산해줍니다.
 연속해서 3칸을 밟을 수 없기 때문에 dp[x][0] = dp[x-1][1]+A[x] 입니다.
 즉 x-1칸에서 1칸 올라와서 x칸을 밟으려면 x-1칸은 2칸올라와서 도착했어야 합니다.