계단오르기
https://www.acmicpc.net/problem/2579 (opens in a new tab)
내 풀이
n = int(input())
costs = []
dp = [0 for _ in range(n)]
for _ in range(n) :
costs.append(int(input()))
steps = [[n-1,1,costs[n-1]]]
while steps :
cur, cnt, cost = steps.pop()
if cur < 0 :
continue
dp[cur] = max(dp[cur], cost)
# cnt가 2번 이하일 때만
# 1칸을 갈 수 있음
if cnt < 2 :
ncnt = cnt + 1
nstep = cur - 1
ncost = costs[nstep] + cost
steps.append([nstep, ncnt, ncost])
ncnt = 1
nstep = cur - 2
ncost = costs[nstep] + cost
steps.append([nstep, ncnt, ncost])
print(dp[0])정답
0, 1, 2번째 계단은 dp의 값이 costs[0], costs[0] + costs[1], max(dp[1], dp[0] + costs[2]) 밖에 경우의 수가 나올 수 없다.
3번째 계단은 max(dp[0] + costs[2] + costs[3], dp[1] + costs[3]) 이렇게 두 가지의 경우가 나올 수 있다.
4번째 계단은 max(dp[1] + costs[3] + costs[4], dp[2] + costs[4]) 이렇게 두 가지의 경우가 나올 수 있다.
이제 규칙이 반복된다. 3번째 계단부터는 dp[i] = max(dp[i-3] + costs[i-1] + costs[i], dp[i-2] + costs[i]) 라는 규칙이 반복되는 것을 알 수 있다. 이를 이용한 풀이 방법은 아래와 같다.
n = int(input())
costs = []
dp = [0 for _ in range(n)]
for _ in range(n) :
costs.append(int(input()))
dp[0] = costs[0]
dp[1] = costs[1] + costs[0]
dp[2] = max(costs[2]+dp[0], dp[1])
for i in range(3, n) :
dp[i] = max(dp[i-3] + costs[i-1] + costs[i], dp[i-2] + costs[i])
print(dp[n - 1])