백준 2579번: 계단 오르기

문제 설명

• 규칙대로 숫자를 더해 가장 큰 값을 만드는 문제입니다.
  • 규칙: 연속된 세 개의 값을 선택할 수 없습니다.

접근법

• 어떤 계단에 도달했을 때 우리에게 주어진 경우의 수는 두 가지 입니다.
  • 1. 연속되지 않은 계단이다.(직전의 계단을 밟지 않았다)
  • 2. 연속된 계단이다.(직전의 계단을 밟았다)

pseudocode

$A(n) = Max(A(n,1),A(n,2))$
$A(n,1) = Max(A(n-2,1),A(n-2,2))+Vn$
$A(n,2) = A(n-1,1)+Vn$

정답

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int[] arr = new int[N];
		for (int i = 0; i < N; i++) {
			arr[i] = sc.nextInt();
		}
		if (N == 1) {
			System.out.println(arr[N - 1]);
		} else {

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

	}
}