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

사용 언어 - Python3

문제 - 계단 오르기

2579번: 계단 오르기

 

 

정답

DP 기초 문제 (정답 맞춘 여부 X)

1. dp = [0]*(n), 0으로 이루어진 리스트 dp 생성

2. 예외처리

계단이 애초에 두개 이하이면, 첫번째 계단+두번째 계단밖에 정답이 없으므로 sum(s)

 

3. 계단이 3개이상인 경우부터 dp에 값 입력

dp[i] = i까지의 계단 최대값

dp[0] = s[0]

dp[1] = s[0]+s[1] 

dp[2]부터는 경우의 수가 늘어난다.

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

마지막 s[i]는 무조건 밟는다고 생각하고, 두가지의 경우를 비교해서 최대값을 현재의 dp에 저장한다.

• dp[i-3]+s[i-1]+s[i] = OXOO, i-3까지의 최대값 + i-1번째 계단값 + i번째 계단값
• dp[i-2]+s[i] = ?OXO, i-2까지의 최대값 + i번째 계단값

4. 가장 오른쪽에 있는 값이 최대값

n=int(input())
s=[int(input()) for _ in range(n)]

dp=[0]*(n)
if len(s)<=2:
    print(sum(s))
else:
    dp[0]=s[0]
    dp[1]=s[0]+s[1]
    for i in range(2,n):
        dp[i]=max(dp[i-3]+s[i-1]+s[i], dp[i-2]+s[i])
    print(dp[-1])

 

 

 

---

레퍼런스

• 동적계획법

한번 푼 문제는 다시 풀지 않는다!

 

[파이썬으로 배우는 알고리즘] 동적 계획법(Dynamic Programming)

• 정답 참고

[백준] 2579 계단 오르기 (DP) - Python / 자세한 설명 / 실버3

• 정답 깃허브

GitHub - yyeongeun/codingtest: 코딩테스트 공부