[백준] 2579 계단 오르기 (Python 파이썬)

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

2579번: 계단 오르기

문제 설명

위 링크에 주어진 문제 설명처럼, 계단을 오르는 문제이다.

단, 3번 연속된 계단을 이어서 오를 수는 없으며

마지막 계단은 무조건 밟아야 한다.

---

풀이 과정

이 문제는 DP(다이나믹 프로그래밍)을 이용해 앞에서 부터 최대값을 저장해 나가야 한다.

현재 계단을 밟는다면, 이전과 이이전을 연속해서 밟으면 안된다.

 

따라서, 현재 계단의 최댓값은 현재 + 이전 + 이이이전 or 현재 + 이이전 중에 선택을 해야한다.

 

한 가지 주의해야 할 점은,

인덱스 에러가 나지 않도록 하기 위해

n = 1일때, 2일때, 3 이상일 때의 케이스를 나눠주자.

n = int(input())
stairs = []
dp = [0]*301
for i in range(n):
    stairs.append(int(input()))

if n > 2:
    dp[0] = stairs[0]
    dp[1] = stairs[0]+stairs[1]
    dp[2] = max(stairs[0] + stairs[2], stairs[1]+stairs[2])
elif n > 1:
    dp[0] = stairs[0]
    dp[1] = stairs[0] + stairs[1]
elif n == 1:
    dp[0] = stairs[0]

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

print(dp[n-1])

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !