[BOJ/DP] 백준 2579 - 계단 오르기 (Java)

2579 - 계단 오르기

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

문제

<계단 오르기 규칙>
1. 한 번에 한 계단씩 or 두 계단씩 오를 수 있음
-> 한 계단 밟으면서 이어서 다음 계단 or 다음 다음 계단
2. 연속된 세 개의 계단 모두 밟아서는 X (시작점 계단에 포함 X)
3. 마지막 도착 계단 반드시 밟아야 함

=> 각 계단에 쓰여 있는 점수 주어질 때, 얻을 수 있는 총 점수의 최댓값?

입력
첫째 줄: 계단의 개수
둘째 줄부터 한 줄에 하나씩 제일 아래에 놓인 순서대로 각 계단에 쓰여 있는 점수 주어짐
계단의 개수(자연수) <= 300, 계단에 쓰여 있는 점수(자연수) <= 10,000
출력: 계단 오르기 게임에서 얻을 수 있는 총 점수의 최댓값

---

풀이

• `int[] arr = new int[n + 1]`: 계단 점수
• `int[] dp = new int[n + 1]`: i번째 계단까지 도달할 때의 최대 점수(누적)
• `dp[i] = Math.max(dp[i - 2], dp[i - 3] + arr[i - 1]) + arr[i]`
  • (1칸) i - 3 -> i - 1 -> i
    
    • (i - 2 -> i - 1 -> i) => 연속 3칸 => X -> i - 2를 건너뜀
    • dp[i - 3] + arr[i - 1] + arr[i]
  • (2칸) i - 2 -> i
    • dp[i - 2] + arr[i]

 

• dp[1] = arr[1] 
  • 0 -> 1 (1칸) => arr[1]
• `if (n >= 2) dp[2] = arr[1] + arr[2]`
  • 1 -> 2 (1칸) => arr[1] + arr[2]
  • 0 -> 2 (2칸) => arr[2]

---

코드

import java.io.*;

public class boj_2579 {
    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[n + 1];
        int[] dp = new int[n + 1];

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

        dp[0] = 0;
        dp[1] = arr[1];

        if (n >= 2) dp[2] = arr[1] + arr[2];

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

        System.out.println(dp[n]);
    }
}