백준 (boj) 파이썬 - 2579 번 : 계단 오르기

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

2579번: 계단 오르기

 

 

 

 

 

 

 

---

 

 

 

 

문제 분류 : 다이나믹 프로그래밍 https://infinitt.tistory.com/246

알고리즘 - 다이나믹 프로그래밍 (Dynamic Programming)

 

 

계단 3칸까지는 명확하다.

계단 i칸까지 오를때의 최댓값을 dp[i] 라고 놓고

문제의 입력(해당 계단의 숫자)를 arr[k] 라고 놓으면

dp [1] = arr[1]

dp [2] = arr[1] + arr[2]

dp [3] = max(arr[1] + arr[3] ,arr[2] + arr[3])

 

4칸째 부터는 생각을 조금 더 해야된다. (3칸 연속되는 계단을 밟을수 없다는 조건때문에)

1. dp[i] = dp[i-2] + arr[i]        -> i칸을 밟기 전의 칸이 i-2이므로 3칸 연속밟을일은 없다.

2. dp[i] = dp[i-1] + arr[i]        -> i칸 이전에 i-1 칸을 밟았으므로, 3칸 연속일 가능성이 존재한다.

따라서 2번 점화식을 바꿔줘야 한다. 한칸 전의 dp가 아닌, 3칸 전의 dp로 이동시킨뒤에 마지막칸은 셀프로 더해주면 3칸 연속일 가능성을 없앨수 있다. 

올바른 2번 점화식 : dp[i] = dp[i-3] + arr[i-1] + arr[i]

 

 

 

결국 최종 점화식은 1과 2중 큰값이 되므로 dp[i] = max ( dp[i-2] + arr[i]   ,  dp[i-3] + arr[i-1] + arr[i] ) 가 된다.

 

*정답 코드(Python)

import sys
input = sys.stdin.readline

N = int(input())
dp = [0 for _ in range(N+3)]
arr = [0 for _ in range(N+3)]
for k in range(1,N+1):
    arr[k] = int(input())


dp [1] = arr[1]
dp [2] = arr[1] + arr[2]
dp [3] = max(arr[1] + arr[3] ,arr[2] + arr[3])


for i in range(4, N+1):
    dp[i] = max( dp[i-3] + arr[i-1] + arr[i] ,  dp[i-2] + arr[i] ) 
print(dp[N])