[BOJ] 백준 [2579] 계단 오르기 JAVA

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

2579번: 계단 오르기

문제

 

풀이

포도주시식 문제랑 비슷하다. 단 , 종결 조건이 정해져있다.

만약 n번째 계단을 갔다고 가정하면 갈 수 있는 경우의 수는 두 가지다.

dp[i] 를 i번째 계단까지 갔을 때 , 얻을 수 있는 점수의 총 합이라고 가정하자.

 

1. 직전 계단을 밟는경우 연속 3번 계단을 건널 수 없으니 => dp[n] = dp[n-3] + n-1계단점수 + n계단 점수

2. 한칸 건너 뛰어 오는 경우 => dp[n] = dp[n-2] + n번째 계단 점수

 

이 둘 중에 큰 값이 되므로 최종 점화식은

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

 

 

import java.io.*;
 
public class Main{
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n+1];
        int[] dp = new int[n+1];
        for(int i=1;i<=n;i++)
            arr[i] = Integer.parseInt(br.readLine());
        dp[1] = arr[1];
        if(n==1){
            System.out.println(dp[1]); //크기가 1일경우 종료
            return;
        }
        dp[2] = arr[1]+arr[2];
        for(int i=3;i<=n;i++)
            dp[i] = Math.max(dp[i-2]+arr[i],dp[i-3]+arr[i]+arr[i-1]);
        System.out.println(dp[n]);
    }
}