백준 - 2579 - 계단 오르기

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

2579번: 계단 오르기

 

동적 계획법 문제이다.

 

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

 

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

public class B_2579 {

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

        int[] stairs = new int[N+1];
        int[] dp = new int[N+1];

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

        dp[1] = stairs[1];

        if(N >= 2){
            dp[2] = stairs[1] + stairs[2];
        }
        for(int i = 3; i <= N; i++){
            dp[i] = Math.max(dp[i-2], dp[i-3] + stairs[i-1]) + stairs[i];
        }
        System.out.println(dp[N]);
    }
}

 

 

처음에 이해가 잘 되지 않아 직접 하나씩 옮겨봤다.

 

 

 

 

 

참고 블로그 :
https://st-lab.tistory.com/132