백준 P2579 계단 오르기 Java 자바

문제

계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. <그림 1>과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다.

<그림 1>

예를 들어 <그림 2>와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다.

<그림 2>

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

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

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

입력

입력의 첫째 줄에 계단의 개수가 주어진다.

둘째 줄부터 한 줄에 하나씩 제일 아래에 놓인 계단부터 순서대로 각 계단에 쓰여 있는 점수가 주어진다. 계단의 개수는 300이하의 자연수이고, 계단에 쓰여 있는 점수는 10,000이하의 자연수이다.

출력

첫째 줄에 계단 오르기 게임에서 얻을 수 있는 총 점수의 최댓값을 출력한다.

---

dp 문제를 스스로 해결하면 너무 뿌듯한 법
알고리즘 스터디 문제로 풀었던 건데 나름 칭찬을 들었기 때문에 오랜만에 공유

문제를 풀고 스터디 당일 날 문제를 헷갈려서 당황했는데
주석으로 정리해 둔 것이 많이 도움이 되었다.
나중에 내가 푼 것들을 까먹을 때가 많은데 앞으로 알고리즘을 풀고 주석을 다는 습관을 들여야겠다.

풀이

풀이는 주석으로 설명을 달았지만 풀어쓰면,
각 계단에 대해 앞 계단을 선택할 경우, 선택하지 않을 경우에 대해 dp 2차원 배열로 저장한다.
각 계단 별로 두가지 경우에 대해 계산을 해주는 것이다.
--> dp[N][2] (N은 계단의 개 수)

3번만 연속으로 밟지 않으면 되므로 2개 까지는 가능한데 현재 계단을 기준으로 앞 계단을 밟으면 앞앞 계단을 밟으면 안되고, 앞 계단을 밟지 않으면
앞앞 계단을 밟아도 된다.

점화식을 표현하면

 sum[i][0] = Math.max(sum[i-2][0], sum[i-2][1]) + scores[i];
 sum[i][1] = sum[i-1][0] + scores[i];

이렇게 표현할 수 있다.
sum[i][0] -> 앞 계단을 선택하지 않았을 경우인데 그러면 앞앞 계단의 누적합 두 개 중 큰 것과 현재 내 계단의 점수를 더한다.
sum[i][1] -> 앞 계단을 선택할 경우는 앞앞계단을 선택하면 안되므로 앞 계단에서 앞 계단을 선택하지 않은 sum[i-1][0] 과 현재 내 계단의 점수를 더한다.

정답 코드

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

public class Main {

    public static void main(String[] args)throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] scores = new int[N+2];

        // 바로 앞 계단을 선택하지 않았을 경우, 바로 앞 계단을 선택할 경우 두 가지 합에 대해 계산.
        // 첫번째 경우는 앞앞 계단의 누적합 중 큰 것과 더하기.
        // 두번째 경우는 앞계단을 선택하려면 앞계단에서는 앞계단을 선택하지 않았어야 하므로 앞계단의 [0]번째 값과 더하기.
        int [][] sum = new int[N+2][2];
        for(int i=2; i<scores.length; i++){
            scores[i] = Integer.parseInt(br.readLine());
            sum[i][0] = Math.max(sum[i-2][0], sum[i-2][1]) + scores[i];
            sum[i][1] = sum[i-1][0] + scores[i];
        }
        int answer = Math.max(sum[N+1][0], sum[N+1][1]);
        System.out.println(answer);
    }
}

1번째 계단에 대해 앞계단과 앞앞 계단의 점수가 없기 때문에 sum 배열을 N+2로 2사이즈 크게 해주었다.
그리고 앞 두개는 비워주고 index 2부터 첫번째 계단의 대한 값이 들어가게 해주었다.

그런데 N이 2이하일 경우는 모든 계단을 선택할 수 있고,
N이 3이상이 경우에 대해 1,2번 계단 값을 미리 초기화해주어 3번 째 계단부터 for문을 돌려주면 sum배열 사이즈를 굳이
늘릴 필요가 없을 것 같은데 N크기에 따라 조건을 추가해주어야 하기 때문에 그냥 이 방법을 선택했다.