백준 Q2579 - 계단 오르기

문제

입력

입력의 첫째 줄에 계단의 개수가 주어진다.
둘째 줄부터 한 줄에 하나씩 제일 아래에 놓인 계단부터 순서대로 각 계단에 쓰여 있는 점수가 주어진다.
계단의 개수는 300이하의 자연수이고, 계단에 쓰여 있는 점수는 10,000이하의 자연수이다.

public class Main {
    public static void main(String[] args)  {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int[] score = new int[n+1];
        for (int i = 1; i <= n; i++) {
            score[i] = sc.nextInt();
        }

        /**
         * 반복문 이용한 풀이 (bottom - up)
         */

        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = score[1];
        if (n >= 2) {
            dp[2] = score[1] + score[2];
        }

        for (int i = 3; i <= n; i++) {
            dp[i] = Math.max(score[i - 1] + dp[i - 3], dp[i - 2]) + score[i];
        }

        for (int i : dp) {
            System.out.print(i+" ");
        }
    }
}

bufferedReader로 입력을 받는것이 아직 미숙하여 Sanner를 통해 입력을 받았다.
또한 시작 state는 값이 0 이므로 dp[0] = 0 으로 초기화하는것은 인지했다 (초기화안해도 0이지만)

이후 dp[1] = score[1] 이 부분을 생각하지 못했는데, 그 이유는
"첫번째 계단을 밟을수도 안밟을 수도 있는 거니까 dp[1]은 초기화하면 안되지" 라는 생각을 했다.

하지만 dp의 핵심은 가장 작은 문제로 쪼개어 생각하는 것이므로
dp[1] 의 값은 우선 step1 을 진행했을 경우니까 무조건 초기화를 해주는 것이 맞다

이후 Math.max 로직에서 dp[1]의 계단을 밟을 껀지 안밟을 껀지를 정해주는것이다.