[백준] 2579번: 계단 오르기

문제

실버3 - 2579번: 계단 오르기

풀이

계단을 오르는 개수를 나열할 떄 연속으로 3개의 계단을 밟으면 안되므로 2칸 또는 (2칸, 1칸)으로 올라가야한다.

즉, dp[i]를 i번째 칸까지 올라갈 때 얻을 수 있는 점수의 최댓값이라고 정의할 때
dp[i] = max(dp[i-2], dp[i-3] + scores[i-1]) + scores[i] 이다.

코드

n = int(input())
scores = [0] * (301)
for i in range(1, n+1):
  scores[i] = int(input())

dp = [0] * (301)
dp[1] = scores[1]
dp[2] = dp[1]+scores[2]

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

원래 scores와 dp를 선언할 때

scores = [0] * (n+1)
dp = [0] * (n+1)

로 선언했다. 하지만 이러면 IndexError가 발생한다.

n=1,2에 대해서 무조건 초기값을 정해주는데 n=1일 경우 dp[2]가 존재하지 않기 때문이다.

따라서

def dynamic_programming(n):
  if n == 1:
    print(scores[1])

  elif n == 2:
    print(scores[1]+scores[2])

  else:
    dp = [0] * (n+1)
    dp[1] = scores[1]
    dp[2] = dp[1]+scores[2]

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

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

dynamic_programming(n)

이런 식으로 아예 초기값 이외의 범위에서만 dp를 선언해주는 방식을 사용하거나, dp의 크기를 n이 최댓값일 때를 기준으로 설정하도록 한다.

정리

• DP문제에서 dp의 크기를 정할 때 n의 최댓값을 기준으로 정의하자