백준 2579 계단오르기

계단오르기 (백준 2579)

https://www.acmicpc.net/problem/2579

점화식을 세우는 것을 연습하였던 문제이다
처음에는 왜 안돼지.. 싶다
0부터 직접 세어보고 규칙을 찾아보았고
이후 점화식을 세워 코드로 구현하여 통과하였다

0부터 센 뒤,
규칙 발견
이후 i에 적용해보고,
코드 작성 후 디버깅

Code

import sys

inp = sys.stdin.readline

n = int(inp().strip())

dp = [0 for _ in range(n + 1)]
val = [0 for _ in range(n+1)]

for i in range(1,n+1):
    val[i] = int(inp().strip())

for i in range(1,n+1):
    dp[i] = max(dp[i-3] +val[i-1] ,dp[i-2]) + val[i]

print(dp[n])

해결 아이디어

1. dp[i] : i번째 계단을 밝았을 때의 최댓값이라 설정
   
2. dp[i-1]을 참조하는 경우를 고려하였지만,
   거의 대부분 규칙을 어기기에
   dp[0]부터 시작하여 점화식을 찾아봄
3. dp[i-2]에서 바로 dp[i]로 넘어올 수 있음
   
4. dp[i-1]에서 dp[i]를 밟을 수 있는 경우는,
   그 전에 i-2를 밟은 것이 아니라, i-3에서 뛰어넘은 경우이므로,
   dp[i-3] + val[i-1]로 정의할 수 있음
5. dp[i] = max(dp[i-3] + val[i-1], dp[i-2]) + val[i] 로 점화식을 세움
   
6. dp[1]과 dp[2]를 초기화하고 값을 넣어도 되지만,
   python의 경우 인덱스가 음수가 되더라도 인덱스 에러가 나지 않고 자동으로 뒤쪽으로 세줌
   (0으로 초기화되어 다소 무시할 수 있음)