알고리즘/Dynamic Programming
BOJ - 2579 ) 계단오르기
개발자가될수있을까?
2019. 12. 15. 21:43
계단을 오르면서 얻을수있는 점수의 최댓값을 구하는 문제이다.
맨 마지막을 꼭 밟으면서 연속된 3개의 계단은 밟지 못하는 규칙이 있으므로
1. 두칸을 오르고 맨마지막 직전의 계단을 밟고 마지막 계단을 밟은경우,
2. 두칸을 오르고 맨마지막 직전 계단 이전을 밟고, 직전계단을 밟고 마지막 계단을 밟은 경우로 나뉜다.
즉 dp[n]값을 구하기위해서 dp[n-2] + num[n] 값과 dp[n-3] + num[n-1] + num[n-2] 값중 큰값으로 업데이트해주면서 진행하면된다.
