백준 SILVER 3 [2579번] 계단 오르기 {언어 : Python}

문제 링크

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

정답 코드

n = int(input())
s = [0] * 301
dp = [0] * 301
for i in range(n):
    s[i] = int(input())
dp[0] = s[0]
dp[1] = s[0] + s[1]
dp[2] = max(s[1] + s[2], s[0] + s[2])
for i in range(3, n):
    dp[i] = max(dp[i - 3] + s[i - 1] + s[i], dp[i - 2] + s[i])
print(dp[n - 1])

풀이 방법

1. n이 1이나 2일 때 인덱스 에러가 걸리지 않게 처음부터 크기가 301인 배열을 만든다.
2. 첫 번째 계단을 오르는 방법은 하나이므로 하나 밖에 없다.
3. 두 번째 계단을 오르는 방법은 두 칸을 연속으로 오르는 방법이 최대이다.
4. 세 번째 계단을 오르는 방법은 한 칸 오르고 두 칸 오르는 방법, 두 칸 오르고 한 칸 오르는 방법 두 가지가 있고 이 중 최대 값을 넣는다.
5. N 번째 계단을 오르는 방법:
   1. 3칸 전의 계단을 오르는 최적의 방법(dp[N - 3]) + 한 칸 전 계단의 score(s[N - 1]) + 현재 계단의 score(s[N])
      • 3칸 전에서 2칸, 1칸으로 움직인 경우
   2. 2칸 전의 계단을 오르는 최적의 방법(dp[N - 2]) + 현재 계단의 score(S(N))
      • 2칸 전에서 2칸으로 움직인 경우
   3. 이 중 최대값을 찾는다.
6. N까지 구하고 dp[N]을 구하면 끝!

느낀점

• 1년전에 푼 문제를 다시 봤는데 어떻게 푸는지 까먹었고 다시 익혀야 겠다는 것을 느꼈다.