[백준 2579] 계단 오르기 (Java)

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

2579번: 계단 오르기

접근 방법

 

DP 방법으로 풀었으며, N번째 계단까지 올라올 때의 경우는 두가지가 있다.

 

첫 번째는 n-1 번째를 밟지 않고 온 경우

두 번째는 n-1 번째를 밟고 온 경우

 

각각의 점화식은 다음과 같으며 이 중 최대값을 골라 dp[] 배열에 넣으면 된다.

 

 

소스 코드

import java.util.Scanner;

public class Main {
    private static int[] stairs;

        public static void main(String[] args) {
            Scanner scanner = new Scanner(System.in);

            int N = scanner.nextInt();
            stairs = new int[N + 1];

            for (int i = 1; i <= N; i++) {
                stairs[i] = scanner.nextInt();
            }

            int[] dp = new int[N + 1];

            dp[1] = stairs[1];

            if (N >= 2) {
                dp[2] = dp[1] + stairs[2];
            }

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

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