[백준][JAVA] 2579: 계단 오르기

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

2579번: 계단 오르기

 

1. dp의 1~3번 째 칸을 미리 채워놓고 for문을 시작하므로 N이 3이하일 경우는 따로 처리해준다.

2. 계단 수가 4이상인 경우 : 4번 째칸 부터 이전 칸들의 점수 최댓값을 이용해 현재 i 칸의 점수 최대값을 계산 한다.

3. dp[i]=Math.max( (dp[i-3] + stair[i] + stair[i-1]), (dp[i-2] + stair[i]) );

 - 1. dp[i-3] + stair[i] + stair[i-1]

        → i-3번 째에서의 최댓값 + (n-1)→(n) 번째 칸을 밟은 경우

 - 2. dp[i-2] + stair[i]

        → i-2번 째에서의 최댓값 + (n) 번째 칸을 밟은 경우 (n-2, n-1, n 연속 밟기 안되므로)

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
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[] stair = new int[N+1];
        int[] dp = new int[N+1];

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

        dp[1]=stair[1];

        if(N<=3){
            if(N==1) System.out.println(dp[1]);
            else if(N==2) System.out.println(stair[1]+stair[2]);
            else System.out.println(Math.max(stair[1]+stair[3],stair[2]+stair[3]));
        }
        else{
            dp[2]=stair[1]+stair[2];
            dp[3]=Math.max(stair[1]+stair[3],stair[2]+stair[3]);

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

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