백준 - 계단오르기[java]

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

문제설명

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

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

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

예제 입력

6
10
20
15
25
10
20

예제 출력

75

문제 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int totalFloors = Integer.parseInt(br.readLine());
        int[] floors = new int[totalFloors + 1];

        for(int i = 1; i < totalFloors + 1; i++) {
            floors[i] = Integer.parseInt(br.readLine());
        }
        dp(floors);
        br.close();
    }

    public static void dp(int[] floors) {

        int [] allcases = new int[floors.length];
        allcases[1] = floors[1];
        if(floors.length > 2)
            allcases[2] = floors[2] + floors[1];
        for(int i = 3; i < floors.length; i++) {
            allcases[i] = Math.max(allcases[i - 2], 
            					allcases[i - 3] + floors[i - 1]) + floors[i];
        }
        System.out.println(allcases[allcases.length - 1]);
    }
}

다이나믹 프로그래밍의 bottom-up 방식으로 풀이했다. 1시간 이상 생각해서 풀이했으나 실패하여 문제풀이 해설을 보고 이해해서 풀었다. 코드를 보니 굉장히 간단한 패턴을 찾으면 되는 문제였는데, dp문제는 좀 많이 연습이 필요할 것 같다.