[BOJ] 백준 2579 계단 오르기

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

 Input 

6

10

20

15

25

10

20

 

 Output 

75

▶ 동적계획법(Dynamic Programming, DP) 

동적계획법(Dynamic Programming, DP)

계단은 아래와 같습니다.　

▶ 10 + 20 + 25 + 20 = 75

 

게임 진행 방식

① 계단은 한 번에 1계단씩 또는 2계단씩 오를 수 있다.

    ex) 첫 번째 계단을 밟고 이어 네 번째 계단으로 올라갈 수 없다.

② 연속된 3개의 계단을 모두 밟아서는 안 된다. 

    단, 시작점은 계단에 포함되지 않는다.

    ex) 첫 번째, 두 번째, 세 번째 계단을 연속해서 모두 밟을 수는 없다.

③ 마지막 도착 계단은 반드시 밟아야 한다.

 

계단 개수(=n)에 따른 밟는 계단 경로는 아래와 같습니다. 

[n = 1]

     → stair[1]

[n = 2]

     → stair[2] + stair[1] 

[n = 3]

    → stair[3] + stair[2]  

    → stair[3] + stair[1]  

[n = 4]

    → stair[4] + stair[2] + stair[1]

    → stair[4] + stair[3] + stair[1]

[n = 5]

    → stair[5] + stair[4] + stair[2] + stair[1] 

    → stair[5] + stair[3] + stair[2]  

    → stair[5] + stair[3] + stair[1]

 

규칙에 따르면 마지막 지점 n번째 계단에 도달하기 직전 밟는 계단은 아래와 같습니다.

ⅰ. stair[n] + stair[n-1] + stair[n-3]

    : stair[n-3] 지점까지 계단을 최대 비용으로 밟은 후 stair[n], stair[n-1]을 추가로 밟는 경우.

ⅱ. stair[n] + stair[n-2]

    : stair[n-2] 지점까지 계단을 최대 비용으로 밟은 후 stair[n]을 추가로 밟는 경우.

 

결국, i번째 계단까지 최대 비용 경로

    → stair[i] + stair[i-1] + dp[i-3]

    → stair[i] + dp[i-2] 

▶ dp[i] = Max(stair[i] + stair[i-1] + dp[i-3], stair[i] + dp[i-2])

 

---

import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
 
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.nextLine());
        int[] stair = new int[n];
         
        // 각 계단의 점수 입력
        for(int i=0; i<n; i++) {
            stair[i] = Integer.parseInt(sc.nextLine());
        }
         
        // 다이나믹 결과 출력
        System.out.println(dynamicFunction(stair));
    }
 
    private static int dynamicFunction(int[] stair) {
        int n = stair.length;
        int[] dp = new int[n];
         
        // 계단 수에 따른 초기값들 처리
        if(n==1) return stair[0];
        else if(n==2) return stair[1]+stair[0];
        else if(n==3) return Max(stair[2]+stair[1], stair[2]+stair[0]);
        else { // n > 3
             
            dp[0] = stair[0];
            dp[1] = stair[0]+stair[1];
            dp[2] = Max(stair[2]+stair[1], stair[2]+stair[0]);
             
            for(int i=3; i<n; i++) {
                dp[i] = Max( stair[i] + dp[i-2] , stair[i] + stair[i-1] + dp[i-3] );
            }
             
            return dp[n-1];
        }
    }
     
    // 두 수 비교 후 큰 값 반환
    private static int Max(int a, int b) {
        return (a > b) ? a:b;
    }
}