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

문제

풀이

dp 배열을 2차원 int 배열로 해서, 현재 step을 VISITED, NOT_VISITED하는 경우 두 가지를 각각 저장했다. 계단을 연속 3개 이상 밟으면 안 된다는 조건때문에 이렇게 했다.

1. step을 밟는 경우는,
   - 2번째 이전 계단을 밟지 않고 바로 전 계단을 밟는 경우
   - 2번째 이전 계단을 밟고 바로 전 계단을 밟지 않는 경우
   이렇게 두 가지가 가능하므로, 둘 중 더 큰 값을 찾아 저장한다.
2. step을 밟지 않는 경우는, 바로 전 계단을 밟은 경우만 유효하므로 이를 저장한다.

이를 코드로 표현하면 아래와 같다.

최초 코드

import java.io.*;

public class Main {

    private static final int MAXIMUM = 300;
    private static final int VISITED = 0;
    private static final int NOT_VISITED = 1;

    private static int n;
    private static int[] costs = new int[MAXIMUM + 1];
    private static int[][] dp = new int[MAXIMUM + 1][2];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        n = Integer.parseInt(br.readLine());
        for (int i = 1; i <= n; i++)
            costs[i] = Integer.parseInt(br.readLine());

        dp();
        bw.append(String.valueOf(dp[n][VISITED]));

        br.close();
        bw.close();
    }

    private static void dp() {
        dp[1][VISITED] = costs[1];
        dp[1][NOT_VISITED] = 0;
        for (int step = 2; step <= n; step++) {
            dp[step][VISITED] = Math.max(dp[step - 2][NOT_VISITED] + costs[step - 1],
                    dp[step - 2][VISITED]) + costs[step];
            dp[step][NOT_VISITED] = dp[step - 1][VISITED];
        }
    }
}

개선 코드

하지만 생각해보니, 1차원 배열로도 이를 표현할 수 있을 것 같았다. 어차피 문제에서도 마지막 계단을 무조건 밟는다는 조건을 주었으니, dp 배열을 1차원 int 배열로 선언하고, step을 밟는 경우의 최댓값을 저장하는 것이다.

1. 3번째 이전 계단을 밟고, 바로 전 계단을 밟는 경우 → dp[step-3] + costs[step-1]
2. 2번째 이전 계단을 밟고, 바로 전 계단은 밟지 않는 경우 → dp[step-2]

private static void dp() {
	dp[1] = costs[1];
	dp[2] = costs[1] + costs[2];
	for (int step = 3; step <= n; step++)
    		dp[step] = Math.max(dp[step - 3] + costs[step - 1], dp[step - 2])
				+ costs[step];
}