[알고리즘/동적 계획법] 2579번 : 계단 오르기 - python

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

2579번: 계단 오르기

 

---

• 문제
• 소요시간: 실패

---

• 설계하기(접근방법)

1. 계단 수, 계단 입력받기, dp선언하기

2. 알고리즘 해석

1) 마지막 계단을 기준으로

i) 전 계단을 밟고 온 경우

-> 이 경우는 전전 계단을 밟고 왔을 경우의 수가 없으니

dp[n] = s[n] + s[n-1] + dp[n-3] 과 같다. s[n-1] + dp[n-3]는 서로 두칸 떨어져있으니 3칸 연속되는 경우는 고려하지 않아도 된다.

 

ii) 전전 계단을 밟고 온 경우 두 가지로 나뉜다.

항상 전전 계단을 밟은 경우는 한번 에(2칸) 뛰어서 와야한다(문제 조건 中 3계단 연속 오르면 안되기 때문) 

dp[n] = s[n] + dp[n-2] 이 경우 역시 두칸 떨어져있으니 3칸 연속되는 경우를 고려하지 않아도 된다.

 

즉 dp[n] = max(s[n] + s[n-1] + dp[n-3] or s[n] + dp[n-2])이다

 

2) 경우의 수

1. 첫 번째 계단

dp[1] = s[1]

2. 두 번째 계단

dp[2] = s[1] + s[2]

3. 세 번째 계단

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

 

4. 네 번째 계단

dp[4] = max(s[1] + s[2] + s[4] or s[1] + s[3] + s[4] )

5. 다섯 번째 계단

dp[5] = max(s[1] + s[2] + s[4] + s[5] or s[1] + s[3] + s[5] or s[2] +s[3]+ s[5])

-> 여기서 알 수 있는 점은

dp[5] = max(dp[2] + s[4] + s[5] or dp[3] + s[5])인 것이다

즉 점화식으로 나타내면

dp[n] = max(dp[n-3] + s[n-1] + s[n] or dp[n-2] + s[n])

 

3)dp[n]을 출력한다.

 

---

• 코드(출력)

n = int(input())

dp = [0] * (n + 4)
s = [0] * (n + 4)

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

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

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

print(dp[n])

---

• 얻어갈 부분

1. 동적 계획법 아이디어가 생각나지 않을 때는 경우의 수를 하나씩 고려해서 점화식을 찾아보자. 혹은 맨 위에서부터 아래로 내려가면서 중복되지 않는 규칙을 찾아본다