백준 - 계단오르기(2579)

⭐문제링크

오늘 풀어볼 문제는 DP의 대명사 문제, 계단오르기 이다!

해당 알고리즘이 너무 약한 거 같아서 골랐다.

🚨문제 풀이시 주의점

1. 무조건 마지막 계단은 밟아야 한다.
2. 계단을 연속해서 3번 밟을 수는 없다.
3. 시작점은 계단이 아니다.

📒풀이

해당 문제를 풀 수 있는 방법은, TOP-BOTTOM / BOTTOM-TOP 2가지의 경우의 수로 나뉜다. 오늘은 DP를 처음 배우는 것이기 때문에 자세하게 경우의 수에 대해 적어보려고 한다.

1. TOP-BOTTON

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

public class Main {

    static Integer dp[];
    static int arr[];

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

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

        dp = new Integer[N + 1];
        arr = new int[N + 1];

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

        dp[0] = arr[0];	// 디폴트값이 null이므로 0으로 초기화 해주어야한다.
        dp[1] = arr[1];

        // N 이 1이 입력될 수도 있기 때문에 예외처리를 해줄 필요가 있다.
        if(N >= 2) {
            dp[2] = arr[1] + arr[2];
        }

        System.out.println(find(N));

    }

재귀함수를 들어가기 전, 배열의 초기화와 기본세팅 부분이다.
dp를 돌때, 현재의 인덱스 부분이 최적화가 되었는지 아닌지 알기 위해 null을 사용해줄 것이므로, dp는 int 배열이 아닌 integer 배열이다.

---

    static int find(int N) {
        // 아직 탐색하지 않는 N번째 계단일 경우
        if(dp[N] == null) {
            dp[N] = Math.max(find(N - 2), find(N - 3) + arr[N - 1]) + arr[N];
        }

        return dp[N];
    }

1. 해당 경우는 무조건 마지막 계단을 포함해야 하므로 Math.max 함수로 최대값을 찾고 난 후 현재 인덱스에 해당하는 계단의 점수를 더해줘야 한다.

2. Math.max의 왼쪽 부분은 현재계단(0)+이전계단(X)+이전이전계단(0) 에 해당하는 경우이다.

3. Math.max의 오른쪽 부분은 현재계단(0)+이전계단(0)+이전이전계단(x)+이전이전이전계단(0)에 대한 경우의 수이다.

한마디로 말하자면, 현재계단 포함시, 연속해서 계단을 밟지 않은 경우(2)와 연속해서 계단을 밟은 경우(3) 중 어느 경우가 더 큰 점수값을 가지는지에 대해 구하는 코드이다!

⭐연속으로 3계단을 밟으면 안되기에 위와 같은 경우의 수가 만들어졌다.
=> 둘의 경우를 아무리 앞뒤로 붙여보아도 연속으로 계단이 0가 되는 경우는 없다는 것을 알 수 있다!

⭐N-1의 계단을 밟은 경우는 특이하게도 dp(N-1)이 아닌 arr(N-1)이다. 이건 경우의 수를 정확히 나누기 위해서이다.

만약 dp(N-1)을 한다면, 해당 N-1의 최적화 된 값을 반환하기 때문에 해당 계단을 밟을 수도, 밟지 않을 수도 있다. 이렇게 되면 우리가 원하던 3번의 "현재 계단(N)을 포함해서 연속적으로" 계단을 밟은 경우에 위배될 수 있다.

---

2. BOTTOM-TOP

해당 경우는 위의 내용을 모두 이해했으면, 코드만 보아도 쉽게 이해할 수 있을 것이다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
 
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[] DP = new int[N + 1];
		int[] arr = new int[N + 1];
        //null 값이 필요없으니 int 배열로 선언했다!
 
 
		for (int i = 1; i <= N; i++) {
			arr[i] = Integer.parseInt(br.readLine());
		}
 
		// index = 0 은 시작점이다.
		DP[1] = arr[1];
		
		// N 이 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]);
 
	}
 
}