[백준] 2579번 : 계단 오르기 (JAVA)

1. 문제 분석

 

이번 문제도 DP를 활용하면 풀 수 있는 문제이다. DP는 매번 느끼지만 코드는 간단한데 점화식 찾는게 제일 어려운 것 같다.

 

시간복잡도 : O(N) 

알고리즘 : DP

2. 문제 풀이

이번 문제에는 조금 까다로운 조건이 붙는다. 계단을 연속해서 등반할 수 없다. N번째 계단에 무조건 도달해야 되기 때문에 N-1, N-2 를 모두 밟는다면 도착점에 도달할 수 없게 된다. 우선 X번째 계단에 올 수 있는 경우는 두가지이다. 이전에 연속 계단을 밟았고 한칸 넘어 오는경우, 이전에 연속해서 밟지 않았기에 바로 전 블록에서 오는 경우.

• 한칸 넘어 올때 : dp[i] = stair[i] + dp[i-2]
• 바로 전 블록에서 오는경우 dp[i] = stair[i] + dp[i-3] + stair[i-1]

두번째 경우에는 특별하게 dp값이 아니라 이전 계단값 + 현재 계단 값까지가 확정이기에 위와 같이 더해준다.

 

3. 코드 구현

import java.io.IOException;
import java.util.Scanner;

public class BOJ_2579 {

    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] stair = new int[N+1];
        int[] dp = new int[N+1];
        for(int i = 1; i <= N; i++){
            stair[i] = sc.nextInt();
        }
        sc.close();

        if(N==1){
            System.out.println(stair[1]);
            return;
        }
        dp[1] = stair[1];
        dp[2] = stair[1] + stair[2];

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

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