[BAEKJOON] 2579번 : 계단오르기 (JAVA)

- 알고리즘 분류 : 다이나믹 프로그래밍, Bottom-Up 방식

- 사용 언어 : JAVA

- 문제 요점

1. 연속 3계단을 밟을 수 없음
2. 마지막 계단은 꼭 밟아야함
3. 시작 지점은 취급 x

- 점화식 도출 

d[i] = Math.max(d[i-3]+arr[i-1] + arr[i], d[i-2] + arr[i]);

(현재 계단을 포함해 연속 2개 밟기 or 이전 계단 건너 뛰고 현재 계단 밟기)

 

소스 설명은 주석을 참고해주세요.

 

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

public class Main {

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		int[] arr = new int[N+1];
		int[] d = new int[N+1];
		
		for(int i=1;i<=N;i++) {
			arr[i] = Integer.parseInt(br.readLine());
		}
		
		// 첫 번째 계단 설정 
		d[1] = arr[1];
		// 계단이 1개만 주어질 수도 있으니 조건문으로 처리 
		if(N>1) {
			d[2] = arr[1] + arr[2];
		}
		
		// 점화식을 이용해 Bottom-Up방식 이용
		for(int i=3;i<=N;i++) {
			d[i] = Math.max(d[i-3]+arr[i-1] + arr[i], d[i-2] + arr[i]);
		}
		
		System.out.println(d[N]);
	}

}