[java 백준] 실버 3/ 2579번 계단오르기

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

2579번: 계단 오르기

import java.util.Scanner;
 
public class Main {
 
    public static int n;
 
    public static int[] arr;
    public static int[] dp;
 
    public static void main(String[] args) {
 
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        arr = new int[n + 3];
        dp = new int[n + 3];
 
        for (int i = 1; i <= n; i++) {
 
            arr[i] = sc.nextInt();
 
        }
        dp[1] = arr[1];
        dp[2] = arr[2] + arr[1];
        dp[3] = Math.max(arr[1] + arr[3], arr[2] + arr[3]);
        for (int i = 4; i <= n; i++) {
            dp[i] = Math.max(dp[i - 3] + arr[i - 1] + arr[i], dp[i - 2] + arr[i]);
        }
 
        System.out.println(dp[n]);
 
    }
 
}
 

https://we1cometomeanings.tistory.com/85

[java 백준] 실버 1/ 2156번 포도주 시식

2156번 포도주시식 문제랑 문제푸는 방식이 비슷했다! 

근데 중요한 것은 마지막 계단은 꼭 밟아야 하는데 첫번째 계단은 굳이 안밟아도 된다!

 

dp[3] = Math.max(arr[1] + arr[3], arr[2] + arr[3]);

그래서 위와 같은 코드가 나오는 것이다.  첫번째 세번째를 밟는경우, 두번째 세번째를 밟는 경우 중 가장 큰 값을 고르면된다. 

 

만일 n이 4이고 계단이 10 20 15 25 순으로 있을 때, 점화식을 세울 수 있는 방법은

 

분홍, 파랑 중에서 더 큰 값을 택하면 된다. 

여기서 첫번째 계단을 더해준 것은 반드시 넣어야 하는 것이 아닌 첫번째 계단을 더해줘야 계산한 값이 더 커지기 때문이다!