[백준] DP_2579 python

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

2579번: 계단 오르기

 

나의 풀이 (틀림)

- 마지막 계단은 꼭 올라야 한다는 조건을 고려해서 마지막 계단에서 거꾸로 내려가는 방식을 생각했다.

- 계단을 한 칸 뛰고 온 건지 두 칸 뛰고 온 건지에 대한 확인하는 변수와 dp를 활용했는데 

- 이전 계단에서 오는 경우에도 dp를 활용하여 에러 난 것 같다.

- 내가 생각한 이 문제의 포인트는 마지막 계단 입장에서 최대의 해를 구할 수 있는 점화식을 세우는 것이다! 이렇게 하면 모든 계단 고려 가능

 

정답 풀이

n = int(input())
s = [0 for i in range(301)]
dp = [0 for i in range(301)]

for i in range(n):
    s[i] = int(input())

dp[0] = s[0]
dp[1] = s[0] + s[1]
dp[2] = max(s[1] + s[2], s[0] + s[2])

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

print(dp[n - 1])

- dp는 i번째가 마지막 계단이라고 했을 때 최대의 합의 경우이다.

- 그래서 한칸전 계단으로부터 온 것인지 두칸 전 계단으로부터 온 것인지 dp 값으로 확인할 수 없어 경우를 나누어서 계산한다.

• 1칸 전 계단으로부터 오는 경우 : dp [i-3] + s [i-1] + s [i] 
  • dp [i-3] : 한 칸 전 계단으로 오기 전 두 칸 전 계단에서의 최대 값
  • s [i-1] : 한 칸 전 계단의 값 (dp를 사용하지 않음!!)
  • s [i] : 현재 값
• 2칸 전 계단으로부터 오는 경우 : dp [i-2] + s [i]
  • dp [i-2] : 두 칸 전 계단에서의 최대 값
  • s [i] : 현재 값

- 최종적으로 dp[n-1]을 출력하여 마지막 계단에서의 최대 값을 구한다 

-> 마지막에서부터 거꾸로 계산하지 않고 마지막 계단까지 dp값을 구한다!