계단 오르기
Prob
계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다.
연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
마지막 도착 계단은 반드시 밟아야 한다.
게임에서 얻을 수 있는 총 점수의 최댓값
Solv
dynamic programming
Check
1. 연속으로 밟은 경우를 기준으로 값 누적
0에는 이전 1과 2중 큰 값
| 0 | 1 | 2 | |
|---|---|---|---|
| 0 | 0 | 0 | |
| 10 | 0 | 10 | |
| 20 | 10 | 20 | 10+20 |
| 15 | 30 | 10+15 | 20+15 |
| 25 | 35 | 30+25 | 25+25 |
| 10 | 55 | 35+10 | 55+10 |
| 20 | 65 | 55+20 | 45+20 |
2. 메모리 최적화
max(pprev,prev)
| dp | |
|---|---|
| 0 | |
| 10 | 10 |
| 20 | 10+20 |
| 15 | max(10,30)+15 |
| 25 | max(30,10+15)+25 |
| 10 | max(45,30+25)+10 |
| 20 | max(55,45+10)+20 |
Feedback
풀이를 적어도 이해가 잘 안된다.
Ref
https://www.youtube.com/watch?v=VA0yKXI80rg
https://yabmoons.tistory.com/20
