백준 / 2579번 / 계단 오르기 / python 파이썬

 

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

 

 

다이나믹 프로그래밍 (DP) 문제이다.  계단을 오르며 얻을 수 있는 최댓값을 구하면 되는 문제이지만 조건이 있다.

1. 한 번에 한 계단 혹은 두 계단씩 오를 수 있다.

2. 연속된 세 개의 계단을 밟을 수 없다.

3. 마지막 계단은 반드시 밟아야 한다.

 

---

이 세 조건을 만족시키며 답을 구하기 위해 다음과 같이 접근하였다.

1. 계단의 개수가 각각 1, 2개일 때

     계단의 점수를 더한 값을 출력한다.

 

2. 계단의 개수가 3개 이상일 때

  1) dp 테이블을 계단의 개수만큼 0으로 초기화하여 만든다.

  2) dp[0] = 첫 번째 계단의 점수 , dp[1] = 첫 번째 계단의 점수 + 두 번째 계단의 점수를 저장한다.

  3) dp[2]에 세 번째 계단을 밟을 때까지의 최댓값을 구하여 저장한다. 

  4) for문을 통해 세 번째 계단 이후부터 각 계단을 밟을 때의 최댓값을 구한다.

 

3. 세 번째 계단 이후부터 각 계단을 밟을 때의 최댓값 구하기

  1) 첫 번째 경로 ( dp[i-2] + stairs[i]) 

      - 두 계단 전에서 현재 계단으로 이동하는 경우 (연속된 두 계단을 밟음)

  2) 두 번째 경로 (dp[i-3] + stairs[i-1] + stairs[i])

     - 세 계단 전에서 한 계단을 건너뛰고 현재 계단으로 오는 경우 (세 계단을 연속으로 밟지 않고 건너뜀)

 

4. 두 경로의 점수 중 최댓값을 dp 테이블에 저장하여 dp[-1] , 총 점수의 최댓값을 구할 수 있다.   

---

 

나의 풀이

n = int(input())

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

if n == 1:
    print(stairs[0])
elif n == 2:
    print(stairs[0] + stairs[1])
else:
    dp = [0] * n
    dp[0] = stairs[0]
    dp[1] = stairs[0] + stairs[1]
    dp[2] = max(stairs[0] + stairs[2], stairs[1] + stairs[2])
    for i in range(3, n):
        dp[i] = max(dp[i-2] + stairs[i], dp[i-3] + stairs[i - 1] + stairs[i])

    print(dp[-1])