[백준] 2579 계단오르기 Python

1. 문제

계단에 쓰여 있는 점수가 주어질 때 점수의 최댓값 구하기
1. 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다 
2. 연속된 세 개의 계단을 모두 밟아서는 안 된다
3. 마지막 도착 계단은 반드시 밟아야 한다

2. 요구 사항

* 계단의 개수는 300 이하의 자연수 

* 계단에 쓰여 있는 점수는 10,000 이하의 자연수 

3. 알고리즘 분류

* 다이나믹 프로그래밍 

4. 접근 방식

계단을 올라가는 것만 생각하지 말고, 이미 올라간 상태에서 

이전에 내가 어떤 계단을 밟고 올라올지를 생각하는 방식으로 접근한다

1) 직전 계단 (n-1) 을 밟고 올라온 경우는 

세번 연속 계단을 오를 수 없으므로 그 이전 계단은 n-3 번째 계단이다

2) 두 칸 전 (n-2) 계단을 밟고 올라온 경우 

 

i 번째 계단까지 올라왔을 때까지의 최대 값을 dp[i] 이라고 두고

각 계단의 점수는 stair[i] 으로 두고 계산한다 

첫번째 경우는 dp[i-3] + stair[i-1] + stair[i] 

두번째 경우는 dp[i-2] + stair[i]

5. 전체 코드 

# 계단에 쓰여 있는 점수가 주어질 때 점수의 최댓값 구하기

# 1. 한 번에 한 계단 또는 두 계단씩 오를 수 있다
# 2. 연속된 세 개의 계단을 모두 밟아서는 안 된다
# 3. 마지막 도착 계단은 반드시 밟아야 한다 

# 직전 계단을 밟고 올라온 경우 그 이전 계단은 n-3 번째
# dp[i-3] + stairs[i-1] + stairs[i]
# 두 칸 전 계단을 밟고 올라온 경우
# dp[i-2] + stairs[i]

n = int(input())
stairs = [0] * 301 # 계단 점수를 저장하는 배열
dp = [0] * 301 # 누적 최대값을 저장하는 배열 

for i in range(1, n+1):
    stairs[i] = int(input()) # 점수 입력 받기 

# 계단이 두 개 밖에 없는 경우 두 개 다 밟아야 하니
# n 이 1 과 2 일 때 기본값 생성 
dp[1] = stairs[1] 
if n > 1:
    dp[2] = stairs[1] + stairs[2]

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

print(dp[n])