계단오르기는 다이나믹으로 해결할 수 있다.
연속해서 오른 계단이 하나인 것과 두개인 것을 계산하여 처리할 수 있다.
1번은 연속해서 오른 계단이 하나인것, 즉 두번 뛰어서 오른 계단에 대한 정보를 확인하는 것이다.
i-2 번째 계단의 1번 연속, 2번 연속해서 오른 계단의 최대값가 현재 계단의 값의 합이다.
2번은 연속해서 오른계단이 두개인것, 즉 이전계단에서 한번오른 것이다.
이전계단에서 한번오른 값과 현재의 값을 더하여 결정한다.
반응형
'알고리즘 > 정올' 카테고리의 다른 글
[정올][분할정복] 1335 색종이만들기 (0) | 2017.04.14 |
---|---|
[스크랩] [정올] 문제 해답 (0) | 2017.04.13 |
[정올][다이나믹] 1407 숫자카드 (0) | 2017.04.13 |
[정올][최단거리] 1108 페이지 전환 (0) | 2017.04.11 |
[정올][다이나믹] 1848 극장좌석 (0) | 2017.04.11 |