[BaekJoon] 백준 2579. 계단 오르기 - Java

 

계단은 한번에 한칸 혹은 두칸을 뛰어넘을 수 있고 한칸씩 뛰어넘을 때 연속으로 3번의 계단을 밟을 수 없다. 

 

N번째 계단에서의 최댓값은 d(n-1) 혹은 d(n-2) 중 최대값과 자신의 가중치를 더한 값이다. 

 

단 연속해서 3번의 계단을 밟을 수 없는데 이는 n-1 계단을 선택하려면 n-1번째 계단이 연속으로 밟은 계단이 아니어야 한다. 

 

d(n-1)을 d(n-3)+n-1번째 계단 값 으로 계산하여 방지할 수 있다. 

 

import java.util.Scanner;

public class Main {
	public static void main(String args[]) {
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
		int max = 0;
		
		int[] stair = new int[n];
		int[] d = new int[n];
		
		for(int i = 0; i<n; i++) {
			stair[i] = scan.nextInt();
		}
		
		d[0] = stair[0];
		if(n > 1)
			d[1] = d[0]+stair[1];
		if(n > 2)
			d[2] = Math.max(stair[1], stair[0])+stair[2];
		if(n > 3) {
			for(int i = 3; i<n; i++) {
				d[i] = Math.max(d[i-3]+stair[i-1], d[i-2])+stair[i];
			}
		}
		System.out.println(d[n-1]);
	}

}