계단 오르기 - 2579

문제

계단 오르는 데는 다음과 같은 규칙이 있다.

계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.
연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
마지막 도착 계단은 반드시 밟아야 한다.
따라서 첫 번째 계단을 밟고 이어 두 번째 계단이나, 세 번째 계단으로 오를 수 있다. 하지만, 첫 번째 계단을 밟고 이어 네 번째 계단으로 올라가거나, 첫 번째, 두 번째, 세 번째 계단을 연속해서 모두 밟을 수는 없다.

각 계단에 쓰여 있는 점수가 주어질 때 이 게임에서 얻을 수 있는 총 점수의 최댓값을 구하는 프로그램을 작성하시오.

풀이

import java.util.Scanner;

// 계단 오르기 - S3
public class Main {

    static int n;
    static int[] stairs;
    static int[] dp;
    public static void solution(){
        dp[0]=0;
        dp[1]=stairs[1];

        if(n>=2) dp[2] = stairs[1] + stairs[2];

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

        System.out.println(dp[n]);
    }
    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();
        }
        solution();
    }
}

명심하자

계단타기 , 뭐 건너기 , 배낭 , 동전 등 최소최대 경우의 수 -> DP문제다

일단 이런 DP문제는 초반 뿌리를 심어놔야 한다. 0번 계단은 없는 걸로 친다고했으니 빼놓고, 첫번째 계단과 두번째 계단을 타는 최대값을 저장해놓는다. 그리고 이제 두번 째로 중요한 점화식을 찾아야 한다.

점화식을 생각해보면 , 3번째 계단을 오른다고 가정해보자. 3번째 계단을 오르는 방법은 0번(바닥)에서 2단 점프를하고 2번째 계단에서 한번 점프해서 3번째 계단 점수를 합하는 것과 , 1번에서 2단 점프를하고 3번째 계단에 바로오는 방법 중 더 큰 최대값을 정해야하므로 Math함수를 이용해서 비교해준다. 계단 시작점은 DP[]에서 점수를 가져오고, 거기에 stairs[]의 점수를 더해준다.