[python]백준 2579번: 계단 오르기(DP)

# 2579 계단 오르기

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

2579번: 계단 오르기

코드

n = int(input())
list_ = [int(input()) for _ in range(n)]
dp = [0] * n

if len(list_) <= 2:
  print(list_)
else:
  dp[0] = list_[0]
  dp[1] = list_[1] + list_[0]
  for i in range(2, n):
    dp[i] = max(dp[i-3]+list_[i-1]+list_[i], dp[i-2]+list_[i])
  print(dp[-1])

📝 풀이

계단을 오르는 데에 다음과 같은 규칙이 있다.

1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.
2. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
3. 마지막 도착 계단은 반드시 밟아야 한다.

첫 번째 계단과 마지막 계단은 무조건 밟아야 하고, 한 계단이나 두 계단씩 오를 수 있으며, 연속해서 세 계단을 밟으면 안된다.

🔓 코드 뜯어보기

n = int(input()) # 계단 개수
list_ = [int(input()) for _ in range(n)] # 계단 리스트
dp = [0] * n # dp 리스트

계단의 갯수 n과 계단 점수 리스트, dp리스트를 각각 만들어준다.

if len(list_) <= 2:
  print(list_)
else: # 계단이 3개 이상이라면
  dp[0] = list_[0] # 첫째 계단
  dp[1] = list_[1] + list_[0] # 둘째 계단
  for i in range(2, n): # 3번째 계단 점화식
    dp[i] = max(dp[i-3]+list_[i-1]+list_[i], dp[i-2]+list_[i])
  print(dp[-1]) # [10, 30, 35, 55, 65, 75]

만약에 계단이 2보다 작다면 여지없이 모두 더해서 출력시켜준다. 

계단이 3개 이상이라면 else문을 실행시켜주고, 첫째 계단과 둘째 계단까지는 수동으로 계산해준다.

핵심코드인 점화식을 쪼개서 살펴보면

dp[i-3] + list_[i-1] + list[i] = i-3까지의 계단 점수 최댓값과 i-1, i 계단의 합이 된다. 즉 i-3까지의 계단의 합과 2계단을 연속으로 걸었을 때이며

dp[i-2], list_[i] = i-2까지의 계단 점수 최댓값과 i 계단의 합이다. 즉, 한 계단을 건너 뛴 것을 비교해서 큰 값을 dp[i]에 저장한다.

위와 같이 dp리스트에 점수의 최댓값을 보장하게 된다.