[백준] 2579번 계단 오르기 _ JAVA ( 주석 설명 )

조건

- 계단을 1칸 or 2칸씩 오를 수 있다.

- 연속 3개의 계단은 오를 수 없다.

- 마지막 계단은 무조건 밟아야 한다.

 

풀이

1) 마지막 계단은 무조건 밟아야 하므로

dp[N] = ? + ary[N] 이어야 한다.

 

2) 최대 2칸의 계단을 오를 수 있으며(한 칸 건너뛰기), 연속 3개의 계단은 오를 수 없으므로 다음과 같은 점화식을 도출할 수 있다.

N-2 까지의 값 vs N-3까지의 값에 직전값(ary[N-1]), 연속되지 않는 위치의 값에 대해서만 비교를 해주어야 한다.

dp[N] = Math.max(solve(N-2), solve(N-3) + ary[N-1]) + ary[N]

 

https://st-lab.tistory.com/132

[백준] 2579번 : 계단 오르기 - JAVA [자바]

 

Top-Down 방식 : 큰 문제부터 작은 문제로 들어가는 방식

→ 재귀 호출을 통해 작은 문제로 쪼개서 들어가는 것


Bottom-Up 방식 : 작은 문제부터 풀어가며 전체 문제를 풀어가는 방식

→ 반복문을 통해 하나씩 풀어가는 것

 

 

---

 

1번 

→ Top-down 방식

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


public class Main {

    static int[] ary; //각 층별로 점수가 몇 점인지 저장하는 공간이다.
    static int[] dp; //각 층별로 계단에서 얻을 수 있는 총 점수의 최댓값을 저장하는 공간이다. => 층수만큼의 공간이 필요함
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine()); //계단의 층(개수)를 입력한다.
        ary = new int[N+1]; //1인덱스부터 시작하기 위해 N+1 공간을 만든다.
        dp = new int[N+1];

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

        System.out.println(solve(N)); //N층에서 얻을 수 있는 총 점수의 최댓값을 출력한다.
    }

    //Top-down 방식
    private static int solve(int N) {
        if(N==0) {
            dp[0] = ary[0]; //1층만 있을 경우, 게임에서 얻을 수 있는 총 점수는 1층 값 그대로이다.
            return dp[N]; //N==0일 경우, dp[0]=0이 되므로 아래 if(dp[N]==0) 조건문에 들어가, IndexOut이 되므로, 바로 0을 리턴해주어야한다.
        }

        else if(N==1)
            dp[1] = ary[1]; //1층만 있을 경우, 게임에서 얻을 수 있는 총 점수는 1층 값 그대로이다.

        else if(N==2)
            dp[2] = ary[1] + ary[2]; //2층만 있을 경우, 게임에서 얻을 수 있는 총 점수는 1층 값 + 2층 값이다.


        if(dp[N]==0){
            dp[N] = Math.max(solve(N-2), solve(N-3)+ary[N-1])+ary[N];
        }

        return dp[N]; //dp에 값이 있을 경우 바로 리턴한다.
    }
}

 

---

 

2번 

→ Bottom-up

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


public class Main {
    static int[] ary; //각 층별로 점수가 몇 점인지 저장하는 공간이다.
    static int[] dp; //각 층별로 계단에서 얻을 수 있는 총 점수의 최댓값을 저장하는 공간이다. => 층수만큼의 공간이 필요함
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine()); //계단의 층(개수)를 입력한다.
        ary = new int[N+1]; //1인덱스부터 시작하기 위해 N+1 공간을 만든다.
        dp = new int[N+1];

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

        dp[0] = ary[0]; //점수 최댓값 계산에 영향을 주지 않는 0을 그대로 넣어준다.
        dp[1] = ary[1]; //1층에서 총 점수의 최댓값은 그대로 1층 값이다.

        if(N>=2) //계단의 층 수가 2층 이상일 경우 dp[2]를 정의해준다.
            dp[2] = ary[1] + ary[2];

        System.out.println(solve2(N)); //N층에서 얻을 수 있는 총 점수의 최댓값을 출력한다.
    }

    //Bottom-up 방식
    private static int solve2(int N) {
        for(int i=3;i<=N;++i){
            dp[i] = Math.max(dp[i-2], dp[i-3]+ary[i-1])+ary[i];
        }
        return dp[N];
    }
}