[백준 자바JAVA] 2579번 - 계단 오르기

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

---

● 문제

문제의 요구사항을 살펴보자

1. 계단을 오를땐 한 계단 또는 두 계단씩만 오를 수 있다

2. 연속된 3개의 계단을 밟으면 안된다(ex. 1층 2층 3층 연속으로 밟기)

3. 마지막 계단은 반드시 밟아야 한다

 

이 문제는 Top-Down 방식보단 Bottom-Up방식이 더 어울릴 것 같아서 Bottom-Up 방식으로 생각해보았다.

계단 1층부터 하나씩 값을 더해가면서 채워나가 마지막 누적 합을 구하면 되는데 인덱스 i일때 두칸 전의 값과 첫칸 전 + 세번째칸 전의 값 중 큰 값을 현재 i의 계단에 저장하여주면된다.

---

● 코드

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[] dp = new int[n + 1];
        int[] arr = new int[n + 1];

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

        dp[1] = arr[1];

        if(n >= 2)
            dp[2] = arr[1] + arr[2];

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

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

    }


}