[백준] 2579번 - 계단 오르기 [Java]

https://www.acmicpc.net/problem/2579

 

[백준] 2579번 - 계단 오르기 [Java]

[백준] 2579번 - 계단 오르기 [Java]

---

1.  아이디어

 

Bottom-Up 다이나믹 프로그래밍을 활용해서 해결했다. 3개의 계단을 연속해서 오를 수 없는 조건은 2칸 이전 계단에서 얻은 최댓값에서 현재 칸에서 얻는 점수와 3칸 이전 계단에서 얻은 최댓값에 1칸 이전에서 얻은 점수와 현재 칸에서 얻은 점수의 합을 비교하면 된다.

---

2. 문제풀이

 

구현의 편의를 위해 배열로 다룰 때 앞쪽에 패딩을 넉넉하게 주는 방식으로 구현했다.

---

3. 코드

 

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        int[] arr = new int[3 + N];
        for (int i = 3; i < N + 3; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }

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

        System.out.println(dp[N + 2]);
    }
}

---

4. 후기