[백준/Java] 2579 계단 오르기

문제

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

풀이방법

마지막은 무조건 밟아야 하므로
N-2 계단이면 dp[i-2] + score[i]
N-1 계단이면 dp[i-3]+dp[i-1]+score[i]
위에서 dp[i-3]을 dp[i-2]로 하면 연속 세계단이라 안됨
점화식은 dp[i] = max(dp[i-2] + score[i], dp[i-3] + score[i-1] + score[i])

풀이

import java.util.*;
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[] score = new int[N+1];
        int[] dp = new int[N + 1];

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

        dp[0] = score[0];
        dp[1] = score[1];
        if (N==1) {
            System.out.println(dp[1]);
            return;

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

}