[BOJ2579] 계단 오르기

총 점수의 최댓값 구하기

• 계단 밟으며 점수 얻기
• 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.
• 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
• 마지막 도착 계단은 반드시 밟아야 한다.

입력

• 계단 갯수 (<= 300)
• 순서대로 제일 아래에 놓인 계단부터 점수 (<= 10,000)

출력

• 얻을 수 있는 총 점수의 최대값

설계

• dp[i] 는 i 번째 계단의 최댓값
• dp[i] = max(stair[i] + stair[i-1] + dp[i-3], stair[i] + dp[i-2])

피드백

• 3번째 인덱스 전까지의 dp 값을 어떻게 넣을지 고민
• 계단 점수 배열을 1부터 시작했을 때(마지막 인덱스 N), 0번의 점수는 0
• 이 때, dp[1] = stair[1] / dp[2] = stair[1] + stair[2]
• 계단 점수 배열을 0부터 시작했을 때(마지막 인덱스 N-1)
• dp[0] = stair[0] / dp[1] = stair [0]+ stair[1] / dp[2] = max(stair[0] + stair[2], stair[1] + stair[2])

How I solved(click to github)

---

ref :
BOJ2579