다이나믹 프로그래밍 점화식

[백준 - Python] 2579번 : 계단 오르기

🌱 문제 https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 💡 설명 필자는 해당 문제를 BFS로 해결하려 했으나 채점 7% 에서 메모리 초과가 발생하였습니다. 아무리 n이 300이라고 해도 주어진 메모리가 128MB인 상황에서 메모리를 많이 요구하는 BFS로 문제를 해결하기에는 문제가 있어 보였습니다. 다음 방법으로 다이나믹 프로그래밍(DP)로 접근을 시도하였습니다. Memoization 기법을 통해 이전에 구한 최적값(해당 층까지 구한 최대 스코어)을 dp..