백준 알고리즘 2579번: 계단 오르기(Python)

 

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

2579번: 계단 오르기

---

문제 해결을 위한 과정

이 문제를 해결하는데 있어서 가장 중요한 것은 마지막 계단을 밟아야 한다는 것이며 첫번째 계단을 밟지 않아도 된다는 것 입니다. 문제의 규칙에 따르면 다음과 같습니다.

1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.
2. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
3. 마지막 도착 계단은 반드시 밟아야 한다.

먼저 계단이 한개일때 최대 점수는 다음과 같습니다.

첫 번째 계단이자 마지막 계단을 밟는 경우 -> 10점

 

계단이 두개일때 최대 점수는 다음과 같습니다.

첫 번째 계단과 마지막 계단을 밟는 경우 ->10 + 20점

 

계단이 세개일때 최대 점수는 다음과 같습니다.

두번째 계단과 마지막 계단을 밟는 경우 -> 20 + 15점

 

계단이 네개일때 최대 점수는 다음과 같습니다.

첫번째 계단과 두번째 계단 및 네번째 계단을 밟는 경우 -> 10 + 20 + 25점

 

다만 세번째 부터 다음과 같은 규칙이 적용되는것을 알 수 있습니다. (단, 마지막 계단이 n번째 일때)

최대의 점수 = max(n번째 계단 + n-2번째 까지의 최대 점수, n번째 계단 + n-1번째 계단 n-3번째 까지의 최대 점수)

이를 소스코드로 표현하면 다음과 같습니다.

---

소스코드

n = int(input())
data = [0] * 301
for i in range(n):
    data[i] = int(input())
 
 
dp = [0] * 301
dp[0] = data[0]
dp[1] = data[0] + data[1]
dp[2] = max(data[2] + data[1], data[2] + data[0])
for i in range(3, n+1):
  dp[i] = max(data[i] + data[i-1] + dp[i-3], data[i] + dp[i-2])
 
print(dp[n-1])