DP: #2579: 계단오르기 [JAVA]

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

2579번: 계단 오르기

 

 

---

 

 

 

문제 접근

 

 

#2156 포도주 시식과 유사

 

 

 

 

 

 

 

 

 

 

코드

 

 

 

 

bottom up - 반복문

 

 

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

public class Main {

	static Integer[] dp;
	static int[] arr;

	public static void main(String[] args) throws IOException {

		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(bf.readLine());

		dp = new Integer[N + 1];
		arr = new int[N + 1];

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

		dp[0] = 0;
		dp[1] = arr[1];

		if (N >= 2) {
			dp[2] = arr[1] + arr[2];
		}

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

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

		bf.close();
	}

}