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

✔ 문제

---

✔ 풀이

🤢 오답 코드1

import sys
input = sys.stdin.readline

n = int(input())
arr = []
dp = [0] * (n+1)

for _ in range(n):
    arr.append(int(input()))

dp[0] = arr[0]
dp[1] = arr[0] + arr[1]
dp[2] = max(arr[0] + arr[1], arr[0] + arr[2])

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

print(dp[n-1])

 

🤢 오답 코드2

import sys
input = sys.stdin.readline

n = int(input())
arr = [0 for _ in range(301)]
dp = [0 for _ in range(301)]

for i in range(n):
    arr[i] = int(input())

dp[0] = arr[0]
dp[1] = arr[0] + arr[1]
dp[2] = max(arr[0] + arr[1], arr[0] + arr[2])

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

print(dp[n-1])

 

😭 정답 코드

import sys
input = sys.stdin.readline

n = int(input())
arr = [0 for _ in range(301)]
dp = [0 for _ in range(301)]

for i in range(n):
    arr[i] = int(input())

dp[0] = arr[0]
dp[1] = arr[0] + arr[1]
dp[2] = max(arr[1] + arr[2], arr[0] + arr[2]) # 현재값+현재-1 값, 현재값+현재-2 값

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

print(dp[n-1])

---

✔ 설명

연속된 세 계단을 밟을 수 없기 때문에 구해야 하는 경우의 수는 2가지로 나뉜다.

1. 현재 + 현재 -1 위치의 값 (2계단 연속)

2. 현재 + 현재 -2 위치의 값

 

따라서 dp[0]은 arr[0]을, dp[1]은 arr[0] + arr[1]의 값을 넣고

dp[2]에서는 위의 경우의 수 2가지 중 더 큰 값을 넣는다.

 

for문을 돌리면서 해당 경우의 수를 직접 수식으로 적어 구현하면 되는데,

dp[3] 의 경우 arr[i-3] + arr[i-2] + arr[i] 또는 arr[i-3] + arr[i-1] + arr[i] 값 중 더 큰 값이 들어가면 된다.

 

arr[i-3] + arr[i-2] + arr[i] 의 경우엔 arr[i-2]까지의 합을 dp[i-2]로 표현할 수 있기 때문에 (현재 위치 기준의 값으로 보면 arr이 맞지만 누적된 값을 구해야하므로 dp[i-2]를 사용해야함) dp[i-2] + arr[i] 로 수식을 바꿔야한다.

arr[i-3] + arr[i-1] + arr[i]의 경우에는 arr[i-3]까지의 합을 dp[i-3]으로 표현하면 된다. 따라서 dp[i-3] + arr[i-1] + arr[i]의 수식이 된다.

 

이 두 값 중 더 큰값을 dp[i]에 대입하면 된다.

---

✔ 후기

for문의 dp 공식은 맞았는데 계속 답이 틀려서 다시 찬찬히 봤더니 dp[2] 공식이 틀렸다.

dp[2] 공식을 고쳐도 index error가 나서 문제를 다시 읽어봤더니 계단의 개수는 300 이하의 자연수라 그래서 dp와 arr를 301로 초기화 해줬다.