백준 2579 계단 오르기 자바

문제는 다음과 같다.
https://www.acmicpc.net/problem/2579

풀이는 다음과 같다.

import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());
        int[] score = new int[301]; //index 계단의 점수

        int[][] dp = new int[301][2]; //dp[i][j] = i번째 계단을 바로 직전에 j+1번 뛰어왔을때 점수

        for(int i = 1 ; i <= N ; i++) {
            score[i] = Integer.parseInt(br.readLine());
        }

        dp[1][0] = score[1];
        dp[1][1] = 0;
        dp[2][0] = score[2] + dp[1][0];
        dp[2][1] = score[2];

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

        bw.write(String.valueOf(Math.max(dp[N][0], dp[N][1])));
        bw.flush();
        bw.close();
    }

}

흔한 DP 문제이다.
DP를 풀기 위해선 세가지를 찾아야 한다.

1. DP 배열 정의
   dp[i][j] = i번째 계단을 바로 직전에 j+1개의 계단을 뛰어왔을때 점수의 최댓값이다.
   
   예를 들어,
   dp[10][1] = 10번째 계단을 이전에 2개의 계단을 뛰어넘어왔을때 점수 최댓값
   dp[10][0] = 10번째 계단을 이전에 1개의 계단을 뛰어넘어왔을때 점수 최댓값
   
   
2. 점화식
   dp[i][1] = i번째 계단 자체 점수 + Math.max(dp[i-2][1], dp[i-2][0])
   내가 이전에 두칸을 뛰어넘어서 현재 i칸에 왔다면,
   문제에서 주어진 조건
   연속된 세 개의 계단을 모두 밟아서는 안 된다. 는 고려할 필요가 없다.
   
   하지만 이전에 한칸을 뛰어넘어서 왔다면, 해당 조건을 고려해야 한다.
   만약 i-1번째 계단을 한칸을 뛰어넘어서 왔다면, (dp[i-1][0]이라면,)
   해당 조건때문에
   다음 칸을 또다시 한칸으로 뛰어넘어 올 수 없게 된다.
   즉, dp[i][0]은 dp[i-1][0]에서 올 수 없다.
   
   생각해보자!
   dp[i-1][0], dp[i][0] 둘 다 한칸씩 뛰어넘어 온 친구들이다.
   그렇다면 dp[i][0]을 dp[i-1][0]에서 오도록 시킨다면,
   
   i-2번째 계단에서 i-1 번째 계단으로 한칸 뛰어서 (dp[i-1][0])
   i-1번째 계단에서 i번째 계단으로 한칸 뛰어서 (dp[i][0])
   이게 되므로 총 연속된 세계의 계단을 모두 밟아버린다.
   
   즉, dp[i][0]은 오직 i-1번째 계단을 두칸을 뛰어서 온 친구에서 비롯되어야 한다.
   dp[i][0] = i번째 계단 자체 점수 + dp[i-1][2]
   
   그 내용이 아래와 같다.

dp[i][1] = score[i] + Math.max(dp[i-2][1], dp[i-2][0]);
dp[i][0] = score[i] + dp[i-1][1];

3. 초깃값 설정. (첫번째)
   첫번째 계단, 두번째 계단은 생각하면 쉽다.
   첫번째 계단은 이전에 한칸만 뛰어올 수 밖에 없다.

dp[1][0] = score[1];
dp[1][1] = 0;

4. 초깃값 설정. (두번째)
   두번째 계단은 이전에 한칸한칸 해서 두번째로 오거나
   두칸을 통째로 뛰어와서 올 수 있다.

dp[2][0] = score[2] + dp[1][0]; //한칸한칸
dp[2][1] = score[2]; //두칸 뛰어버리기