백준 -2579번 - 계단 오르기

2579번

import java.io.*;
import java.util.*;

public class Main {

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

	static int LIS(int N) {

		if(dp[N] == null) {

//			if (N == 3) {
//				dp[3] = Math.max(arr[1], arr[2]) + arr[3];
//			} else {
				dp[N] = Math.max((LIS(N-3) + arr[N-1] + arr[N]), (LIS(N-2) + arr[N]));

//			}
		}
		return dp[N];
	}

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		int num = Integer.parseInt(bf.readLine());

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

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

		}

		System.out.println(LIS(num));

	}

}

풀이

1. N-3까지의 최댓값 + N-1번째 수 + N번재 수
2. N-2까지의 최댓값 + N번째 수

마지막 계단을 무조건 밟아야 하므로 1번과 2번 중 큰 수를 출력하면 된다.