[BOJ 2579] 계단오르기

문제

• BOJ 2579
• 문제의 저작권은 Baekjoon Online Judge에 있습니다.

접근방식

현재 계단에서 구할 수 있는 최대값은 이전 계단 or 전전 계단을 선택한 두가지 경우의 수로 구할 수 있다.
이전 계단을 선택한 경우 연속 세개의 계단은 밟을 수 없으므로, 현재 인덱스가 i라면 i-1, i-3 계단을 밟을 수 있다.
이때, i-3계단을 오르기 까지 최대값을 DP배열에 저장해둔다면 i번째 계단에서의 최대 점수는 stairs[i]+stairs[i-1]+dp[i-3]가 된다.
전전 계단을 선택한 경우 현재 인덱스가 i라면 i-2 계단을 밟을 수 있다.
따라서 i-2계단을 오르기 까지 최대값을 DP배열에 저장해둔다면 i번째 계단에서의 최대 점수는 stairs[i]+dp[i-2]가 된다.
따라서, 이 두가지 경우 중 최대값을 선택한다면 현재 계단에서 최대 점수를 구할 수 있다.

코드

import java.util.Scanner;

//계단 오르기
//처음=>재귀: 시간초과
public class Main {

    static int N; //계단의 개수
    static int[] stairs;
    static int[] dp; //현재 계단에 올랐을때 최대값

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        stairs = new int[N+1];
        dp = new int[N+1];

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

        dp[1] = stairs[1];
        if(N >= 2) dp[2] = stairs[1] + stairs[2]; //계단이 한개일 수 있으므로

        //직전칸과 전전칸 중 최대값 저장
        for(int i=3; i<=N; i++) dp[i] = Math.max(stairs[i]+stairs[i-1]+dp[i-3], stairs[i]+dp[i-2]);
        System.out.println(dp[N]);
    }
}