백준 2579번 계단 오르기 파이썬 문제 풀이 + 팁

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

2579번: 계단 오르기

 

이 문제는 기본적으로 설명이 개떡같다...

조건을 이해하기 쉽게 설명하자면

 

계단은 한 칸을 오르거나 두 칸을 오를 수 있다

연속해서 한 칸을 오르는 것은 불가능하며 두 칸은 얼마든지 마음대로 올라가는 것이 가능하다

마지막 계단은 반드시 밟아야 하며 첫번째 계단은 계단에 포함시키지 않는다

즉 첫번째 두번째 계단을 연속해서 밟아도 되지만 첫번째부터 세번째를 이어서 밟지는 못한다

사실 문제는 별로 어렵지 않은데 문제를 잘못 읽어서 생기지 않아도 될 문제가 생겨버린...그런 문제였다

그리고 계단의 개수가 자연수라고만 언급 되어있는데

이 말은 계단이 하나인 경우도 있다는거다

 

 

 

 

풀이 코드는 다음과 같다

n = int(input())

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

if n > 0 :
  dp = [[]]* n
  dp[0] = [scores[0], scores[0]]
if n > 1 :
  dp[1] = [dp[0][0] + scores[1], scores[1]]
if n > 2 :
  for i in range(2,n) :
    dp[i] = [dp[i-1][1]+scores[i] , max(dp[i-2])+scores[i]]
  

print(max(dp[n-1]))

해당 풀이에서는 각 칸에 도착 할 때 얻을 수 있는 점수를 두 가지 조건으로 저장한다

앞은 한 칸을 올랐을 때, 뒤는 두 칸을 올랐을 때이다

한 칸을 올라가려면 무조건 앞의 칸에서는 두 칸을 올라와야한다

그러므로 한 칸을 올라왔을 때의 점수는 앞 칸에서 두 칸을 올라왔을 때의 점수에서 해당 칸의 점수를 더한다

두 칸을 올라온 경우는 연속해서 두 칸을 올라왔을 수도, 한 칸을 올라가고 두 칸을 올라갔을 수도 있기 때문에

두 칸 앞의 계단에서 한 칸을 올라온 경우와 두 칸을 올라온 경우의 최대값에서 해당 칸의 점수를 더한다

 

이런 방법으로 마지막 칸 까지 점수를 계산하고

마지막 칸에 한 칸을 올라온 경우와 두 칸을 올라온 경우 중 최대값을  반환하면 된다