[알고리즘] 백준 - 계단 오르기

백준 - 계단 오르기

내 풀이

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

public class baekjoon_2759 {
    static int[] arr;
    static int[] dp; //dp[i]를 i번째를 밟았을때 i번째까지 최고 점수
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        arr = new int[n + 10];
        dp = new int[n + 10];

        for (int i = 1; i < n + 1; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }
        dp[1] = arr[1];
        dp[2] = arr[1] + arr[2];
        dp[3] = Math.max(arr[1] + arr[3], arr[2] + arr[3]);
        System.out.println(solve(n));
    }

    private static int solve(int curPos) {
        if (dp[curPos] == 0) {
            dp[curPos] = Math.max(solve(curPos - 3) + arr[curPos-1], solve(curPos - 2)) + arr[curPos];
        }
        return dp[curPos];
    }
}

dp[i]를 i번째를 밟았을 떄 i번째까지 최고 점수라고 정의했다. 그러면 dp[i] = Math.max(dp[i]-2, dp[i-3] + arr[i-1]) + arr[i]가 된다. dp[i-1]을 사용하지 못하는 이유는 dp[i-1]의 값이 두번 연속으로 밟아서 얻은 값일 수 있기 때문이다. 만약 dp[i-1]을 이용하면 dp[i]가 세 번 연속으로 밟은 값일 수가 있다.
따라서 dp[i-3]을 얻고, 직접 arr[i-1]을 더해주는 방식을 사용했다.

dp 문제를 풀다보면 dp[i-3] 같은 곳에서 index error를 신경써야하는데 여기서는 dp와 arr를 넉넉하게 할당해서 문제를 해결했다. 이렇게되면 비록 n이 3보다 작더라도 신경쓰지 않아도 된다.