[CLASS 3: DP] 백준 2579 계단 오르기

2579번: 계단 오르기

https://www.acmicpc.net/problem/2579

 

# 코드

import java.io.*;

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];

        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]);
    }
}

• 현재 인덱스 i 에 대해 두 칸 전(i - 2)의 '메모이제이션 값'과 첫 칸 전(i - 1)의 값 + 셋 째칸 전(i - 3)의 '메모이제이션 값' 중 큰 값을 현재 i 계단의 값과 합하여 DP배열에 저장(Memoization)을 해주면 된다고 한다.

 

코드는 아래 블로그를 참고했다.

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