알고리즘/정올
[정올][다이나믹] 1520 계단오르기
hs_seo
2017. 4. 13. 16:11
계단오르기는 다이나믹으로 해결할 수 있다.
연속해서 오른 계단이 하나인 것과 두개인 것을 계산하여 처리할 수 있다.
1번은 연속해서 오른 계단이 하나인것, 즉 두번 뛰어서 오른 계단에 대한 정보를 확인하는 것이다.
i-2 번째 계단의 1번 연속, 2번 연속해서 오른 계단의 최대값가 현재 계단의 값의 합이다.
2번은 연속해서 오른계단이 두개인것, 즉 이전계단에서 한번오른 것이다.
이전계단에서 한번오른 값과 현재의 값을 더하여 결정한다.
반응형