[백준][Java] 2579번 계단 오르기 (DP)

실수한 부분

1. DP[1], DP[2] 초기화

2. N이 1인 경우에는 DP[2]가 존재하지 않음 (ArrayIndexOutOfBound Exception 방지)

3. 점화식 DP[i] = Math.max(

                    DP[i-2],

                    DP[i-3]+score[i-1])

                    + score[i];

 

이 부분의 DP[i-3]+score[i-1]은 DP[i-1]이 아님.. DP[i-1]이 더 큰 개념

DP[i-1]은 DP[i-2] + score[i-1] 또는 DP[i-3] + score[i-1] 둘 중 하나임..

개념을 좁혀준거임 'DP[i]로 오기 전에 2칸을 뛰었습니다'라는 조건을 점화식에 담아준 것

이걸 안 담아주고 DP[i-1]을 점화식에 넣어버리면

문제에서 요구하는 조건인 세 칸을 연속해서(한칸씩) 건너갈 수 없습니다 라는 조건을 만족하지 못함

 

4. Top-Down 재귀에서 계속해서 들어가면서 Down하려면

아직 구하지 않은 DP[x] 값을 null같은 값으로 표시를 해줘야함

(null을 쓰려면 Integer로 선언해야 했기에 -1로 표현함)

 

 

Top-Down(재귀)

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
 
 
public class Main {
        
    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    
    private static int[] DP;
    private static int[] score;
    private static int find(int n){
        
        if(DP[n]==-1) {
            DP[n] = Math.max(find(n-2), find(n-3)+ score[n-1]) + score[n];
        }
        
        return DP[n];
    }
    
    public static void main(String[] args) throws IOException{
        int N = Integer.parseInt(br.readLine());
        
        score = new int[N+1];
        for(int i=1; i<=N; i++){
            score[i] = Integer.parseInt(br.readLine());
        }
        
        DP = new int[N+1];
        Arrays.fill(DP,-1); // 이걸로.. 안 구한 DP를 지나치는 일이 없게함 
        
        DP[0] = 0;
        DP[1] = score[1];
        if(N>=2) DP[2] = score[1]+score[2]; // block ArrayIndexOutOfBoundsException
        
        System.out.println(find(N));
        
//        bw.write("");
//        bw.flush(); 
//        bw.close();
    }
}

 

 

 

Bottom-Up