[백준/Python] 2579 계단 오르기

[백준/Python] 2579 계단 오르기

정답 코드 및 설명

전체 코드

import sys

# 입력을 빠르게 받기 위한 설정
input = sys.stdin.readline

n = int(input())
stairs = [int(input().strip()) for _ in range(n)]

# dp 배열 초기화
dp = [0] * n
dp[0] = stairs[0]
if n > 1:
    dp[1] = stairs[0] + stairs[1]
for i in range(2, n):
    dp[i] = max(dp[i-2] + stairs[i], dp[i-3] + stairs[i-1] + stairs[i])

print(dp[n-1])

코드 설명

1. 계단 점수 입력 받기

import sys
input = sys.stdin.readline

n = int(input())
stairs = [int(input().strip()) for _ in range(n)]

입력을 빠르게 받기 위해 sys 를 사용했고, staris 를 입력 받는 부분을 간략하게 list comprehension 을 사용했다.

2. dp 배열 초기화

dp = [0] * n
dp[0] = stairs[0]
if n > 1:
    dp[1] = stairs[0] + stairs[1]

동적 프로그래밍을 위해서 dp 배열을 생성하고 0번째를 제일 처음에 있는 계단으로 하고, dp[1] 은 n 이 1보다 클 때 첫번째 계단 점수와 두번째 계단 점수를 합한 값으로 설정한다.

3. 점화식을 이용하여 계산

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

문제에서 계단을 오를 때 두 가지 주요 규칙을 생각해야한다.

• 한 계단을 오르는 경우

• 두 계단을 오르는 경우

  이에 더해서 연속 세 계단을 밟지 않는 규칙을 준수해야한. 따라서 마지막으로 밟을 계단을 기준으로 이전 계단을 밟았는지, 아니면 두 계단 전에 밟았는 지에 따라 경우를 나누어 점화식을 결정한다.

• 한 계단을 오르는 경우
  dp[i-2] + stairs[i]
  i-2 번째 계단에서 직접 i 번째 계단으로 뛰어넘어 오르는 상황이다. 즉, i-1 번째 계단은 건너 뛰고 i 번째 계단으로 직접 오르는 것이다.

• 두 계단을 오르는 경우
  dp[i-3] + stairs[i-1] + stairs[i]
  i-3 번째 계단에서 i-1 계단을 거쳐 i 번째 계단을 오르는 상황을 나타낸다. 이는 연속해서 세 계단을 밟지 않고 마지막 두 계단을 연속해서 밟아 오르는 경우이다. 이 경우 i-1 번째와 i 번째 계단의 점수를 모두 더한다.

점화식 부분이 이해 되지 않는 다면 참고 링크에 설명이 잘되어있다.