백준 2579. 게단 오르기 :: 돼지개발자

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

"DP 쓸 때, dp값과 map에 값을 활용해보자.."

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class Main {
 
    static int N;
    static int[] dp;
    static int[] map;
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        N = Integer.parseInt(br.readLine());
        
        dp = new int[N];
        map = new int[N];
        
        for (int i = 0; i < N; i++) {
            map[i] = Integer.parseInt(br.readLine());
        }
        
        if(N == 1) {
            System.out.println(map[0]);
            return ;
        }
        else if (N == 2) {
            System.out.println(map[0]+map[1]);
            return ;
        }
        
        // dp 초기값
        dp[0] = map[0];
        dp[1] = map[0]+map[1];
        dp[2] = Math.max(map[0] + map[2] , map[1] + map[2]);
        
        // 점화식 
        // dp[n] = dp[n-3] + map[n-1] + map[n]
        // dp[n] = dp[n-2] + map[n]
        for (int i = 3; i < N; i++) {
            dp[i] = Math.max(dp[i-3] + map[i-1], dp[i-2]) + map[i];
        }
        
        System.out.println(dp[N-1]);
    }
}