[백준] 2579 계단 오르기 (실버3)

https://www.acmicpc.net/problem/2579
그리디 방식

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        ArrayList<int[]> score = new ArrayList<>();

        for(int i=1;i<=n;i++){
            int val = Integer.parseInt(br.readLine());
            score.add(new int[]{val,i});
        }
        score.sort((a,b)->Integer.compare(b[0],a[0]));
        int sum = 0;
        boolean[] vis = new boolean[n+1];
        vis[n] = true;

        for(int[] s:score){
            // arraylist에서 젤 큰 값 하나씩 빼기
            int val = s[0];
            int index = s[1];
            // 그 인덱스의 좌우로 선택이 안되었다면 sum에 합치고 true만들기
            boolean isThreeConsecutive = false;
            // Case 1: [i-2], [i-1], [i]
            if(index>2 && vis[index - 2] && vis[index - 1]){
                isThreeConsecutive = true;
            }
            // Case 2: [i-1], [i], [i+1]
            if (index > 1 && index < n && vis[index - 1] && vis[index + 1]) {
                isThreeConsecutive = true;
            }
            // Case 3: [i], [i+1], [i+2]
            if (index < n - 1 && vis[index + 1] && vis[index + 2]) {
                isThreeConsecutive = true;
            }
            if (!isThreeConsecutive) {
                vis[index] = true;
                sum += val;
            }
        }
        System.out.println(sum);
    }
}

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] stair = new int[n+1];

        for(int i=1;i<=n;i++){
            stair[i] = Integer.parseInt(br.readLine());
        }
        
        stair[0] = stair[n];
        int index = n;
        int step = 0;

        while ((index-2)>=0){
            // 인덱스 가능한지 확인
            if(step !=2 && stair[index-1]>stair[index-2]){
                stair[0] += stair[index-1];
                index -= 1;
                step += 1;
            } else{
                if((index-2)==0){
                    if(step!=2) stair[0] += stair[index-1];
                    break;
                }
                stair[0] += stair[index-2];
                index -= 2;
                step = 0;

            }
        }


        System.out.println(stair[0]);
    }
}

오답 =>
dp

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] stair = new int[n+1];

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

        int[] dp = new int[n+1];
        if(n==1){
            System.out.println(stair[1]);
            return;
        }
        
        dp[1] = stair[1];
        dp[2] = stair[1]+stair[2];

        for(int i=3;i<=n;i++){
            dp[i] = Math.max(dp[i-2]+stair[i], dp[i-3]+stair[i-1]+stair[i]);
        }

        System.out.println(dp[n]);
    }
}

문제 이해를 잘 못 함. 3개가 안된다는게 연속 두칸을 올라갈 수 있는 경우를 따져서 복잡하게 생각해서 안되었음

한 칸 전에 왔다면 두칸 전을 거쳐 왔어야 함