728x90 반응형 백준 25791 [백준/Python] 2579 계단오르기 | 다이나믹프로그래밍(DP) 📒 문제 🤸♀️ 문제 분석 연속 세 개의 계단을 이동할 수 없다는 것은 한칸->한칸 이동이 불가능 하다는 것이다. 1) 두칸 이동 2) 두칸 이동 후, 한칸의 이동만 가능하다. 정리하자면, i 번째 계단에 오기 위해서는 1) i-2번째 계단(두칸전) -> i 번째 계단 2) i-3번째 계단(세칸전) -> i-1번째 계단(한칸전) -> i 번째 계단 둘 중 하나이다. 그림 설명!!!! 나는 방법1은 나름 납득이 되었는데, 방법2에서 i-3은 dp에서 i-3까지의 최대값을 가져오고, i-1번째는 그냥 배열의 값을 가져와서 더해주는 게 이해가 안됐다. 그냥 i-1번째까지의 최대값을 가져오면 되는 것이 아닌가! 싶었는데 i-1번째까지의 최댓값만 구하면 계속 한칸씩만 이동할 것이고 그렇다면 세 칸의 계단을 연속.. 2022. 3. 30. 이전 1 다음 728x90 반응형
