[BOJ/Silver3] 2579번 계단 오르기 - JAVA[자바]

난이도 : 실버 3

유형 : DP(동적 계획법)

링크 : https://www.acmicpc.net/problem/7569

구현 시간 : 30분

 

 

 

 

 

문제풀이

위 문제는 전형적인 DP 문제 유형이다. 풀이는 반복문을 사용한 Bottom-Up 방식으로 해결하였고, Top-Down 방식은 다른 분들의 코드를 참조하여 작성했다.

 

우선 위 문제를 풀기 위해서는 점화식을 정의해야한다.

 

DP[i] 번째의 최대 점수를 구하기 위해서는 DP[i-2] (두 개의 계단 전의 최대 점수) 와 DP[i-3] + stair[i-1] (세 개의 계단 전의 최대 점수 + 직전 계단의 점수) 간의 최대 값과 stair[i] (i 번째 계단의 점수) 를 더하면 구할 수 있다.

 

A(i) = max(A(i-2), A(i-3) + K(i-1)) + K(i)

 

따라서 위와 같은 점화식을 세울 수 있다. 위 점화식을 코드로 구현하면 아래와 같다.

 

 

 

 

1차 시도 - 통과 (Bottom-Up)

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

        // 계단 점수 저장
        int[] stair = new int[T + 1];
        int[] dp = new int[T + 1];

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

        dp[1] = stair[1];
        if (T > 1) dp[2] = stair[1] + stair[2];

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

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

 

 

 

2차 시도 - 통과 (Top-Down)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    static int[] stair;
    static int[] dp;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

        // 계단 점수 및 dp 배열 초기화
        stair = new int[T + 1];
        dp = new int[T + 1];
        Arrays.fill(dp, -1); // dp 배열 초기화 (-1은 아직 계산되지 않음을 의미)

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

        System.out.println(findMaxScore(T));
    }

    // 최대 점수를 계산하는 재귀 함수
    private static int findMaxScore(int step) {
        // Base Case: 계단이 없는 경우
        if (step <= 0) return 0;

        // Base Case: 첫 번째 계단
        if (step == 1) return stair[1];

        // 이미 계산된 경우 메모이제이션 결과 반환
        if (dp[step] != -1) return dp[step];

        // 점화식: dp[step] = max(dp[step-2], dp[step-3] + stair[step-1]) + stair[step]
        dp[step] = Math.max(findMaxScore(step - 2), findMaxScore(step - 3) + stair[step - 1]) + stair[step];

        return dp[step];
    }
}