*Java) 2579번 계단 오르기 (dp)

 

이 문제의 핵심은 두 가지 경우의 수를 생각하는 것입니다.

1. 바로 직전 계단을 밟지 않고 이전 계단과 현재 계단을 밟는 경우: (2칸) 
2. DP[i - 2]​
3. 바로 직전 계단을 밟고 현재 계단을 밟는 경우: (i-3에서 2칸을 올라오고 i-1에서 한 칸을 올라옴)

    DP[i - 3] + arr[i - 1]) + arr[i]​

        DP[i-3]이 1칸+1칸으로 올라오는 경우가 있기 때문에 2칸을 올라간다.

 

import java.util.Scanner;

public class Main {
 
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
 
		int N = in.nextInt();  // 계단의 개수 입력
 
		int[] DP = new int[N + 1];  // 최대 점수를 저장할 DP 배열
		int[] arr = new int[N + 1];  // 각 계단의 점수를 저장할 배열
 
		for (int i = 1; i <= N; i++) {
			arr[i] = in.nextInt();  // 각 계단의 점수 입력
		}
        
		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]);  // 게임에서 얻을 수 있는 총 점수의 최댓값 출력
 
	}
 
}