[백준] 계단 오르기 2579번 JAVA

계단 오르기 문제는 주어진 점수를 가진 계단을 밟으며 최대 점수를 얻는 문제입니다. 이 문제를 해결하기 위해 동적 프로그래밍(Dynamic Programming)을 사용하여 효율적으로 접근해보겠습니다.

문제 설명

계단을 오르는 데는 다음과 같은 규칙이 있습니다.

• 한 번에 한 계단씩 또는 두 계단씩 오를 수 있습니다.
• 연속된 세 개의 계단을 모두 밟을 수는 없습니다.
• 마지막 도착 계단은 반드시 밟아야 합니다.

예를 들어, 다음과 같은 점수를 가진 6개의 계단이 있다고 가정해보겠습니다.

이 경우, 가능한 최대 점수는 75점입니다.

점화식

첫 번째 계단을 밟고 두 번째 계단까지는 dp[1] = floors[1]
두 번째 계단까지는 dp[2] = floors[1] + floors[2]
세 번째 계단부터는 아래의 점화식을 사용합니다.

궁금한 점?

dp[i] = Math.max(dp[i - 2], dp[i - 3] + dp[i - 1]) + floors[i];

문제의 규칙에서는 연속된 세 계단을 밟을 수 없기 때문에 바로 이전 계단인 dp[i - 1]의 값을 사용할 수 없습니다.
만약 dp[i] = Math.max(dp[i - 2], dp[i - 3] + dp[i - 1]) + floors[i] 로 계산하면, dp[i - 1]이 포함되면서 연속된 세 계단을 밟을 가능성이 생깁니다. 예를 들어 dp[4]를 구할 때 dp[3] + dp[2]처럼 계산이 되어 연속된 세 계단을 밟게 될 수 있습니다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

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

        int T = Integer.parseInt(br.readLine().trim());

        int[] floors = new int[T + 1];
        int[] dp = new int[T + 1];

        for(int i = 1; i < floors.length; i++){
            floors[i] = Integer.parseInt(br.readLine());
        }
        if(T >= 1) dp[1] = floors[1]; // 첫 번째 계단의 점수
        if(T >= 2) dp[2] = floors[1] + floors[2]; // 첫 번째와 두 번째 계단의 합

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

        bw.write(dp[T] + "\n");
        bw.flush();
        bw.close();
        br.close();
    }
        
}