백준 2579번 계단 오르기(JAVA,DP)

<풀이방식>
점프하는 경우 : stair[i] + stair[i-1] + dp[i-3]
점프 안하는 경우 : stair[i] + dp[i-2]

이 두가지 중에서 MAX값을 취하면서 DP배열에 저장한뒤
마지막 DP(n) 을 출력.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int n = sc.nextInt();
		int[] stair = new int[n+2];
		int[] dp = new int[n+2];

	
		for(int i = 1; i <= n; i++)
			stair[i] = sc.nextInt();

		dp[1] = stair[1];
		dp[2] = stair[1] + stair[2];
		for(int i = 3; i <= n; i++) {
			//점프하는 경우 : stair[i] + stair[i-1] + dp[i-3]
			//점프 안하는 경우 : stair[i] + dp[i-2]
			dp[i] = Math.max(stair[i] + stair[i-1] + dp[i-3], stair[i] + dp[i-2]);
		}
		
		System.out.println(dp[n]);
	}
}



좋은 웹페이지 즐겨찾기