[백준/BOJ] 백준 코딩 알고리즘 2579번 계단 오르기 Python (다이나믹 프로그래밍)

 

첫 번째 풀이 (3%에서 틀렸습니다.. ㄱ-)

import sys
input = sys.stdin.readline

N = int(input())
stairs = [0] * N
dp = [0] * N

for i in range(N):
  stairs[i] = int(input())

for i in range(N):
  if i == 0:
    dp[0] = stairs[0]
  elif i == 1:
    dp[1] = stairs[0] + stairs[1]
  elif i == 2:
    dp[2] = max(dp[1], max(stairs[0] + stairs[2], stairs[1], stairs[2]))
  elif i == 3:
    dp[i] = max(dp[i-1], max(dp[i-2] + stairs[i], dp[i-3] + stairs[i-1] + stairs[i]))
  elif i == N - 1:
    dp[i] = max(dp[i-2] + stairs[i], stairs[i-1] + stairs[i])
  else:
    tmp = []
    tmp.append(dp[i-3] + stairs[i-1] + stairs[i])
    tmp.append(dp[i-1] + stairs[i])
    tmp.append(dp[i-4] + stairs[i-2] + stairs[i])
    dp[i] = max(dp[i-1], max(tmp))

print(dp[-1])

 

두 번째 풀이 (정답)

import sys
input = sys.stdin.readline

N = int(input())
stairs = [0] * N
dp = [0] * N

for i in range(N):
  stairs[i] = int(input())

for i in range(N):
  if i == 0:
    dp[0] = stairs[0]
  elif i == 1:
    dp[1] = stairs[0] + stairs[1]
  else:
    dp[i] = max(dp[i-2] + stairs[i], dp[i-3] + stairs[i-1] + stairs[i])

print(dp[-1])

첫 번째 풀이에서 사실 이미 규칙은 찾았는데, 끝값들의 경우를 고려하느라 세부적인 조건들을 나눴고

그에 따라 틀렸습니다가 나왔던 것 같다

 

그래서 다른 사람들의 풀이를 보고, 내가 잘못 푼 부분들을 찾아 수정하였다

 

또한  else 조건에서

어차피 마지막 계단은 무조건 밟아야 하기 때문에

계속해서 계단을 밟는 경우만 고려함으로써 연산을 단순하게 만들었다

 

(첫 번째 풀이에서는 마지막 계단은 꼭 밟고, 그 외에는 안밟는 경우도 있는 것을 포함했더니 괜히 더 코드가 복잡해진 것 같다)

 

또한 두 번째 풀이를 작성하던 도중, 다른 사람들의 코드를 참고했을 때

dp[i-3] 가 매우 신경쓰였는데

왜냐하면 i가 2일 때 dp[-1]가 되기 때문에 잘못된 값을 갖고 오는거 아닌가?! 라고 집착했다

 

하지만 곰곰히 생각해보니, 어차피 dp배열은 이미 0으로 가득 차있도록 선언했고

아직 마지막 자리에 다른 값이 업데이트 되지 않은 시점이기 때문에

0이 더해지므로 변화가 없다는 것...................

 

여기서 머리를 얻어맞은 것 같았다...

 

 

계속해서 공부해도 여전히 어려운 DP ~ 

그래도 끝까지 가보자고.. 킵 고잉 🤣

 

 

참고

https://bio-info.tistory.com/158

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