백준 - 2579(계단 오르기) - DP - Java

1. 문제

https://www.acmicpc.net/problem/2579

2. 풀이

i번째를 기준으로 내려가야한다. 즉 항상 생각을 현재 계단을 기준으로 그 전에서 얼마만큼 올라왔을까를 생각해야하는데, 연속해서 밟지 못하는 것을 어떻게 처리해야할지 굉장히 난감했다. 점화식은 계속해서 세워보고, 풀어봐야 아는 것 같다.

10 20 15가 있을때,

dp[i] = 15 + dp[i-2] // 즉 전에꺼 안밟고 와서 연속되지 않도록.
arr[i] + arr[i-1] + dp[i-3] // 즉 내꺼, 내 전에꺼 밟고 i-3번째의 
dp를 구하는 것이다.

15를 밟고 어떻게 처리해야하나 생각했는데, dp[i-3] + arr[i-1] + arr[i]와 같은 방법으로 해결할 수 있는 것이였다.

✨핵심 Point

N이 1일 경우 stairs[2]가 없기 때문에 예외처리를 진행해주었다.

3. 코드

import java.util.*;

public class Main {

	public static void main(String[] args) {
		
		Scanner input = new Scanner(System.in);
		
		int N = input.nextInt();
		
		int stairs [] = new int[N+1];
		int dp [] = new int [N+1];
		
		for(int i = 1; i <= N; i++) 
			stairs[i] = input.nextInt();
		
		//dp[1] = 1;
		dp[1] = stairs[1];
        
        if(N>=2)
            dp[2] = dp[1] + stairs[2];
		
		for(int i = 3; i <= N; i++) {
			
			dp[i] = Math.max(dp[i - 2] + stairs[i], stairs[i] + stairs[i - 1] + dp[i - 3]);
		}
		
		System.out.println(dp[N]);
	}
}