2579
-
[Python] 백준 2579 계단 오르기알고리즘/문제풀이 2021. 9. 11. 21:33
1. 문제 링크 https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 2. 문제 요약 계단에 점수가 있을 때 게임에서 얻을 수 있는 점수의 최댓값을 구한다. 단 3개 이상의 연속된 계단은 안됨! 3. 아이디어 정리 dp[i][j] 정의: 현재까지 j개의 계단을 연속해서 밟고 i번째 계단까지 올라섰을 때 최댓값. i 계단은 밟음 점화식 (연속으로 최대 2개만 가능하니 아래 두 점화식이 나온다.) dp[i][1] = max(dp[i - 2][1], dp[i - 2]..