DP - 백준2579 계단 오르기

첫 번째 풀이
점화식 구하기
1. 한 번에 1계단 or 2계단
n(테이블) = n(점수) + max(n-1, n-2)(테이블)
2. 연속 세 개는 X
n+3(테이블) = n(테이블) + n+1(점수) or n(테이블) + n+2(점수) or n+1(테이블) + n+2(점수)
점화식 : n = max((n-3 + n-2) or (n-3 + n-1) or (n-2 + n-1))

import java.io.*;
import java.util.*;
public class Main{
    static int[] table;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int stairsN = Integer.parseInt(br.readLine());
        int[] stairs = new int[stairsN];
        for(int i = 0; i < stairsN; i++){
            stairs[i] = Integer.parseInt(br.readLine());
        }      
        //점화식찾기
        //점화식: n = max((n-3 + n-2) or (n-3 + n-1) or (n-2 + n-1))
        //메모이제이션 테이블 생성
        table = new int[stairsN];
        //초기값 정하기
        table[0] = stairs[0];
        table[1] = stairs[0] + table[1];
        table[2] = stairs[2] + Math.max(table[0], table[1]);
        //테이블 채우기
        for(int i = 3; i < stairsN; i++){
            int case1 = table[i-3] + stairs[i-2];
            int case2 = table[i-3] + stairs[i-1];
            int case3 = table[i-2] + stairs[i-1];
            int max = Math.max(case1, case2);
            max = Math.max(max, case3);
            table[i] = max;
        }
        System.out.println(table[stairsN-1]);
        //테이블 채우기
        //점화식 어렵게 생각하지말고, 항상 n을 기준으로 생각하면 쉽게 나옴
    }
}

오답 -> 점화식이 틀린듯

정답
점화식
n번째까지 오는 2가지경우
1. n번째 계단과 n-1번째 계단이 연속되는 경우
n = n-3 + n-1 + n
2. 연속되지 않게 n번째 계단에 도착하는 경우
n = n-2 + n

import java.io.*;
import java.util.*;
public class Main{
   static int[] table;
   public static void main(String[] args) throws IOException{
       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       int stairsN = Integer.parseInt(br.readLine());
       int[] stairs = new int[300];
       for(int i = 0; i < stairsN; i++){
           stairs[i] = Integer.parseInt(br.readLine());
       }      
       //점화식찾기
       //1. 연속된 경우 n = n + n-1 + n-3
       //2. 연속되지 않은 경우 n = n + n-2  
       //메모이제이션 테이블 생성
       table = new int[300];
       //초기값 정하기
       table[0] = stairs[0];
       table[1] = table[0] + stairs[1];
       table[2] = Math.max(stairs[0] + stairs[2], stairs[1] + stairs[2]);
       //테이블 채우기
       for(int i = 3; i < stairsN; i++){
           table[i] = Math.max(
               table[i-3] + stairs[i-1] + stairs[i], table[i-2] + stairs[i]
           ) ;
       }
       System.out.println(table[stairsN-1]);
       //테이블 채우기
   }
}

• 주의할 점
  n = n-3 + n-1 + n 에서, 우항은 table[n-3] 과 stairs[n-1] 과 stairs[n]임
  table[n-3]은 지금까지 더해온 것이고, stairs[n-1]은 거기다가 새로 하나 더한 것, stairs[n]도 그 다음에 새로 더한 것

• 그리고 table[2]를 채울 때도 우항은 stairs[1] + stairs[2]임
  table[1] + stairs[2]로 쓴다면 3개가 연속되는 상황이 발생함

* 점화식 어렵게 생각하지말고, 항상 n을 기준으로 생각하면 쉽게 나옴