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

---

1. 코드

import sys
"""
            모든 계단을 무조건 방문할 수 있는 DP 테이블 구성
            2번째 계단까지는 기본값을 설정해주고 3번째 계단부터 반복문 탐색

            계단    점수        1번연속          2번연속
            1      10         10              0 
            2      20         20              (10+20)=30     
            3      15         (10+15)=25      (20+15)=35                                 
            4      25         (30+25)=55      (25+25)=50               
            5      10         (35+10)=45      (55+10)=65      
            6      20         (55+20)=75      (45+20)=65

"""
n = int(sys.stdin.readline().rstrip())
stairs = [0]
for _ in range(n):
    stairs.append(int(sys.stdin.readline().rstrip()))
if n == 1:
    print(stairs[1])
elif n == 2:
    print(stairs[1] + stairs[2])
else:
    dp = [[0, 0] for _ in range(n + 1)]
    dp[1][0] = stairs[1]
    dp[2][0] = stairs[2]
    dp[2][1] = stairs[1] + stairs[2]
    for i in range(3, n + 1):
        # 연속 한 번
        dp[i][0] = max(dp[i - 2][0], dp[i - 2][1]) + stairs[i]  # 문제<그림1> ex) max(20->25, 10->20->25)
        # 연속 두 번
        dp[i][1] = dp[i - 1][0] + stairs[i]
    print(stairs)

---

2. 후기

1차원 DP로 풀 경우, 마지막 계단을 방문하지 않은 경우를 판별할 수 없다. 그래서 모든 계단을 방문한다고 가정하는 2차원 DP 테이블을 구성해야 한다.

테이블 리스트의 0번째 인덱스는 2칸을 건너 뛰어서 현재 계단을 연속 1번째로 방문하는 경우이다. 이 때 코드를 보면 max값을 사용했는데, 4번째 계단을 방문하는 경우
(1번->2번->4번, 2번->4번) 중 큰 점수값을 사용하는 것이다. 어짜피 2칸을 점프하기 때문에 두 경우 모두 연속된 3개의 계단을 방문하지 않는다.
1번째 인덱스는 바로 이전의 계단 다음으로 현재 계단을 방문하여 연속 2번째로 방문하는 경우를 저장한다. 1, 2번째 계단은 위의 조건을 충족시킬 수 없으므로 따로 초기값을 설정한다.

느낀점: 1차원 DP로 풀리지 않는다면 2차원 DP로 접근하는 생각을 해보자