[백준]2579번: 계단 오르기

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

2579번: 계단 오르기

---

step: 계단별로 점수를 저장할 배열

dp: 해당 계단을 마지막으로 밟을 때까지 누적된 최고점수를 저장할 배열

 

계단 규칙

• 계단은 한 번에 한 칸 또는 두 칸씩 이동할 수 있다.
• 그러나 연속된 세 개의 계단을 밟을 수는 없다.

위 규칙을 지키면서 i번째 칸을 꼭 밟아야 하는 경우를 생각해보자.

 

현재 위치한 칸까지 누적된 최고점수 dp[i]를 계산하는 방법은 두 가지가 있다.

 

1. 직전 칸 밟지 않기

 이 경우 간단하다.

 dp[i] = (현재 칸의 점수) + (i-2번째 칸까지 누적된 최고점수) = step[i] +  dp[i-2]

 

2. 직전 칸 밟기

(i-1)번째 칸을 밟는 경우, 문제에서 제시한 규칙을 만족하기 위해서 i-2번째 칸은 밟을 수 없고, i-3번째 칸은 무조건 밟아야 한다.

따라서 dp[i] = (현재 칸의 점수) + ((i-1)번 칸의 점수) + ((i-3)번 칸까지 누적된 최고점수) = step[i] + step[i-1] + dp[i-3]

 

---

즉, 점화식을 세워보면

dp[i] = max ( step[i]+dp[i-2], step[i]+step[i-1]+dp[i-3] )

 

점화식은 i>=3 인 경우에만 만족하므로 dp[0]~dp[2]는 따로 초기화를 시켜준다.

(배열이 0부터 시작하므로 계단 번호는 0부터 센다)

 

0번 칸: dp[0] =step[0]

 

1번 칸:

1번 칸을 밟으려면 다음 두 가지 경우 중 하나를 고르면 되는데,

0번 칸을 밟는 게 무조건 이득이다.

따라서 dp[1] = step[1] + step[0]

 

2번 칸:

2번칸을 밟을 수 있는 경우는 계단 조건에 따라 위 두 가지 경우이다.

둘 중 더 큰 값을 고르면 된다.

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

 

---

파이썬 코드

import sys
input = sys.stdin.readline

n = int(input())
step=[]
for i in range(n):
  step.append(int(input()))

if n<=2:
  print(sum(step))
  exit()
if n==3:
  print(max(step[0]+step[2],step[1]+step[2]))
  exit()
  
dp = [0]*n
  
dp[0]=step[0]
dp[1]=step[1]+step[0]
dp[2]=max(step[2]+step[1], step[2]+step[0])

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

print(dp[-1])