백준 2579: 계단오르기 해설- python

✏️ 문제

2579번: 계단 오르기

2579

 

✏️ 풀이

 

계단오르기

케이스는 두가지로 분리된다. 이전에 두 계단을 연속으로 오른 경우. 그리고 3계단 이전에는 두계단을 오르고 바로 이전에서 현지점까지 연속으로 올라오는 경우.

본 문제에서는 리스트를 두개 만들었다. i번째 계단까지 최대값을 저장하는 dp[] & 문제에서 준 계단점수를 저장하는 arr[]

이를 점화식으로 나타내보면 아래와 같을 것이다.

 

1. dp[i-2] + arr[i]

2. dp[i-3] + arr[i-1] + arr[i]

 

n=int(input())
arr=[] # 계단 점수
dp=[]

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

#아래 수식에 i-3들어가니까 index범위 맞추기위해 3까지 하드코딩 
dp.append(arr[0])
dp.append(max(arr[0]+arr[1], arr[1]))
dp.append(max(arr[0]+arr[2], arr[1]+arr[2]))

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

print(dp.pop())

해당 풀이는 IndexError가 발생한다. 이전에 https://duckracoon.tistory.com/entry/%EB%B0%B1%EC%A4%80-2748%EB%B2%88-%EB%9F%B0%ED%83%80%EC%9E%84%EC%97%90%EB%9F%ACIndexError

백준 2748번 런타임에러(IndexError)

와 같은 이유에서이다. 계단이 1개인 경우에 arr[2]가 존재하겠는가? 

 

코드 반복되는거 불펴하긴한데 우선 그냥 케이스분리로 해결해두긴했다.

# dp배열: i번째 계단까지 최대값을 저장
# arr배열: 문제에서 주어진 계단점수 저장
# 케이스분리
# 이전에 두계단을 연속으로 오른 경우
# 3계단 이전에서는 2계단을 오륵 바로 이전에서 현재까지 연속

n=int(input())
arr=[] # 계단 점수
dp=[]

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

if n==1:
  dp.append(arr[0])
  print(dp.pop())
elif n==2:
  dp.append(arr[0])
  dp.append(max(arr[0]+arr[1], arr[1]))
  print(dp.pop())
elif n==3:
  dp.append(arr[0])
  dp.append(max(arr[0]+arr[1], arr[1]))
  dp.append(max(arr[0]+arr[2], arr[1]+arr[2]))
  print(dp.pop())

else:
  #아래 수식에 i-3들어가니까 index범위 맞추기위해 3까지 하드코딩 
  dp.append(arr[0])
  dp.append(max(arr[0]+arr[1], arr[1]))
  dp.append(max(arr[0]+arr[2], arr[1]+arr[2]))

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

  print(dp.pop())