[BOJ_2579]계단오르기(실버 3) - JAVA

DP특집

---

🐾 알고리즘

• 동적계획법
• dp 배열이 i번째까지 올라갔을 때의 최고 점수가 갱신하는 과정을 담은 것임을 잊지말자.

---

🐾 생각 포인트

• 아래 부분에서 생각을 오래했다. 그래서 동적계획법에 대해 더 이해하게 되었다..!

for(int i=4;i<N+1;i++){
    //i==4일때, dp[i-3]+stairs[i-1]은 1번계단, 3번계단을 오른 경우고,
    //dp[i-2]는 1번계단과 2번계단을 오른 경우다.
    dp[i] = Math.max(dp[i-3]+stairs[i-1], dp[i-2])+stairs[i];
}

 

• 그리고 dp[1] 과  dp[2] 일때는 정해져있는 값이다.
• ArrayIndexOutOfBound 오류가 난다면 n==1일때나 n==2, n==3일때 에러가 난다는 점이니 조건을 잘 설정해주고 System.exit를 시켜주자.(사실 exit을 시켜주는게 맞는지는 확실하지 않다.)

---

🐾 소스코드

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

public class Main {
    static int[] stairs;
    static int N;
    static int ans;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        stairs = new int[N+1];
        int[] dp = new int[N+1];
        for(int i=1;i<=N;i++){
            stairs[i] = Integer.parseInt(br.readLine());
        }

        dp[1] = stairs[1];
        if(N==1){
            System.out.println(dp[1]);
            System.exit(0);
        }
        dp[2] = stairs[1]+stairs[2];
        if(N==2){
            System.out.println(dp[2]);
            System.exit(0);
        }

        dp[3] = Math.max(stairs[1],stairs[2]) + stairs[3];
        if(N==3){
            System.out.println(dp[3]);
            System.exit(0);
        }

        for(int i=4;i<N+1;i++){
            //i==4일때, dp[i-3]+stairs[i-1]은 1번계단, 3번계단을 오른 경우고,
            //dp[i-2]는 1번계단과 2번계단을 오른 경우다.
            dp[i] = Math.max(dp[i-3]+stairs[i-1], dp[i-2])+stairs[i];
        }
//        System.out.println(Arrays.toString(dp));
        System.out.println(dp[N]);


    }



}

---

😵‍💫 공부해야 할 점

• DP 문제가  알고리즘  대세라고 하니 열심히 공부할  것.
• 깊이 공부할 것.