[백준] 2579: 계단 오르기

문제

문제풀이

주어진 규칙중에서 한번에 세번 연속으로 계단을 건널 수 없으므로 i번째 계단에서 고려해야 할 사항은 i-1번째 계단을 건널 것인가 아닌가이다.

i-1번째 계단을 건널 경우, 고려해야할 사항은 i-2번째 계단은 건너면 안된다. 그러므로 이에 대한 코드는 i-3번째 계단을 건너고 i-1, i번째 계단을 건너도록 하면 된다.

• dp[i-3] + arr[i-1] + arr[i]

i-1번째 계단을 건너지 않는 경우, i-2번째 계단을 건너고 i번째 계단을 건너면 된다.

• dp[i-2] + arr[i]

dp는 둘 중 최대값으로 정해진다.

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

마지막 계단을 건너야 한다는 조건이 있으므로 dp[N]의 최댓값을 출력하면 된다.

코드

import java.util.Scanner;

public class ANS2579 {

    static int N;
    static long[] dp, arr;

    public static void main(String[] args){

        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();

        //배열 선언 및 초기화
        arr = new long[N+2];
        dp= new long[N+2];
        arr[0] = 0;
        for(int i = 1 ; i <= N; i++){
            arr[i] = sc.nextInt();
        }

        dp[0] = arr[0];
        dp[1] = arr[1];
        dp[2] = arr[1] + arr[2];

        for(package DP;

import java.util.Scanner;

        public class ANS2579 {

            static int N;
            static long[] dp, arr;

            public static void main(String[] args){

                Scanner sc = new Scanner(System.in);
                N = sc.nextInt();

                //배열 선언 및 초기화
                arr = new long[N+2];
                dp= new long[N+2];
                arr[0] = 0;
                for(int i = 1 ; i <= N; i++){
                    arr[i] = sc.nextInt();
                }

                dp[0] = arr[0];
                dp[1] = arr[1];
                dp[2] = arr[1] + arr[2];

                for(int i = 3 ; i < N+1; i++){
                    dp[i] = Math.max(dp[i-2] + arr[i], dp[i-3] + arr[i-1] + arr[i]);
                }


                System.out.println(dp[N]);
            }
        }
        int i = 3 ; i < N+1; i++){
            dp[i] = Math.max(dp[i-2] + arr[i], dp[i-3] + arr[i-1] + arr[i]);
        }


        System.out.println(dp[N]);
    }
}