[DP] 백준 2579 계단오르기(Climbing Stairs)

BackJoon 

#2579 - 계단오르기(Climbing Stairs)

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

대표적인 DP문제입니다.

DP[N] 을 N개 계단을 계단오르기 규칙에 의해 얻은 가장 큰 점수라고 하겠습니다.

N번째 계단은 무조건 밟아야 하기 때문에 N번째 계단이 1번 연속인 경우! N번째 계단이 2번연속인 경우! 이 2가지 경우를 나누어서 생각해 보겠습니다. 저는 1차원 배열로 DP를 잡고 풀었습니다.

A 배열은 주어진 계단 점수를 담고 있습니다.

N번째 계단이 1번 연속인 경우 N-1번째 계단은 필요 없고, N-2번째 계단의 총점을 합쳐야 합니다. 따라서..

DP[N] = DP[N-2] + A[N] 

N번째 계단이 2번 연속인 경우 N-1번째 계단은 밟아야 하고, N-2번째 계단은 무조건 밟으면 안되며, N-3번째 계단은 무조건 밟아야 하기 때문에 N-3번째 계단까지 얻은 점수를 더해주면 됩니다.

따라서..

DP[N] = A[N]+A[N-1]+DP[N-3] 

이제 위 점화식 컨셉을 코드로 옮겨보면 다음과 같습니다.

package BackJoon;

import java.util.Arrays;
import java.util.Scanner;

public class ClimbingStairs {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		
		int dp[] = new int[n+1];
		int a[] = new int[n+1];
		
		for(int i=1; i<=n; i++){
			a[i] = sc.nextInt();
		}

		dp[1] = a[1];
		if(n >= 2) dp[2] = dp[1]+a[2];
	
		for(int i=3; i<=n; i++){
			dp[i] = Math.max(dp[i-2]+a[i],dp[i-3]+a[i-1]+a[i]);	
		}
		
		System.out.println(dp[n]);
		
		
	}

}